# Finding the first base that makes 16 prime and 97 a square

• Jun 4th 2013, 07:39 PM
Finding the first base that makes 16 prime and 97 a square
Hi guys.

I recently encountered this problem in a math competition and still have no idea how to solve it, as I suck at number theory. Can anybody explain the solution to me? I know the answer is 53.

What is the smallest base b where 16 is prime and 97 is a square?
• Jun 4th 2013, 08:13 PM
chiro
Re: Finding the first base that makes 16 prime and 97 a square

I'm not exactly sure ewhat you mean. Prime numbers are prime irrespective of the base. You could write 16 in base 10 or 8 and it would still be prime.

Do you instead mean that if you write something in some base then the number in that base if you treated it as a number in base 10 is prime given the base 10 value (and not the intrinsic value)?
• Jun 4th 2013, 08:28 PM
Re: Finding the first base that makes 16 prime and 97 a square
Quote:

Originally Posted by chiro

I'm not exactly sure ewhat you mean. Prime numbers are prime irrespective of the base. You could write 16 in base 10 or 8 and it would still be prime.

Do you instead mean that if you write something in some base then the number in that base if you treated it as a number in base 10 is prime given the base 10 value (and not the intrinsic value)?

I will clarify. If you convert 16 base b back into base 10, it will be prime. if you convert 97 base b back into base 10, it will be a perfect square.
• Jun 4th 2013, 08:39 PM
chiro
Re: Finding the first base that makes 16 prime and 97 a square
In that case, for something base b you have for a two digit number x3*b^2 + x2*b + x3 = some number and if you "interpret" it as base 10 then it means x3*10^2 + x2*10 + x3 has specific properties (like being prime).

For a perfect square this means that the above = t^2 (for some integer t) or it is prime after conversion into base 10.

You have the number in base b as 97 for the square and you have the square values.

Given that there are a limited number of squares to test, you should be able to get a few equations in terms of b and solve these equations.

To start off, I'll get you to write out the two equations: one for the square and one for the prime so that you get b's in terms of other numbers.
• Jun 4th 2013, 08:50 PM
Re: Finding the first base that makes 16 prime and 97 a square
It is easy to see that 6 + b is prime and 9b+ 7 is a square, but I have no idea what to do with these. I know there is a way to limit how many square numbers to test, but I am unsure of that as well.
• Jun 4th 2013, 08:54 PM
chiro
Re: Finding the first base that makes 16 prime and 97 a square
What is the maximum number of digits you can have and how does that restrict the number of square numbers? (For example if you are limited to less than three digits, then you can only have 9 possibilities).
• Jun 5th 2013, 06:51 AM
johng
Re: Finding the first base that makes 16 prime and 97 a square
Hi,
The attached solution is not elegant, but it's not hard.

Attachment 28531
• Jun 5th 2013, 10:17 AM
johng
Re: Finding the first base that makes 16 prime and 97 a square
Hi again,
I got curious about such bases. So I quickly wrote a little C program to find such. The program finds 12 such bases less than 10000, the last being 9473. I was mildly surprised that so many exist. I used floating point arithmetic to test if a given integer is a perfect square. This in general is not a good idea, but for "small" integers it's okay. Here's the code, if you're interested:

Code:

#include <stdio.h>
#include <math.h>
#define MAX 10000

int isPrime(int p);

int main() {
int b=11,s,numberFound=0;
double x;
while (b<=MAX) {
if (b%3==0) {
b+=2;
continue;
}
if (!isPrime(b+6)) {
b+=2;
continue;
}
x=sqrt(9*b+7);
s=(int)floor(x);
if (s*s==9*b+7) {
printf("base is %d, prime is %d. square is %d = %d squared\n",
b,b+6,9*b+7,(int)x);
numberFound++;
}
b+=2;
}
printf("%d bases found <= %d\n",numberFound,MAX);
return(0);
}

/* Returns 1 (true) iff p is prime.  Upon entry, p is odd.  If p is not prime and d is the smallest proper
divisor of p, clearly d*d<=p.
*/
int isPrime(int p) {
int d=3;
while (d*d<=p) {
if (p%d==0) {
return(0);
}
d+=2;
}
return(1);
}

• Jun 5th 2013, 10:35 AM
Re: Finding the first base that makes 16 prime and 97 a square
Is there anyway of knowing that the smallest possible base will not be in the hundreds or thousands? Cause brute forcing is fine, but it could potentially take a very long time if the smallest value of b was much higher.
• Jun 5th 2013, 05:46 PM
johng
Re: Finding the first base that makes 16 prime and 97 a square
I assume you mean generalizing the problem to:
Given positive integers $\displaystyle k,d_0 \text{ and }d_1$, find the smallest base b with $\displaystyle b>k,b>d_1,b>d_0,b+k\text{ prime and }d_1b+d_0\text{ a perfect square}$

I don't think there is any easy way to do this. If there were, in particular, one could easily find the smallest prime larger than 2k for a given k -- oops, very hard problem.
• Jun 6th 2013, 11:04 PM
allthehomework
Re: Finding the first base that makes 16 prime and 97 a square
Quote:

Hi guys.

I recently encountered this problem in a math competition and still have no idea how to solve it, as I suck at number theory. Can anybody explain the solution to me? I know the answer is 53.

What is the smallest base b where 16 is prime and 97 is a square?

I literally spent the last 24 hours mulling this problem over. It's not that it's hard to do with a spread sheet, or just brute forcing it with a calculator. However, I'm assuming that in a math competition calculators are not allowed and that time is of the essence. So the real challenge is how do you handle the problem in the most efficient way?

Obviously my long explanation takes more time than is necessary, but the point is if you have this background knowledge before the competition you could get it with little actual calculation.

So we have b+6 = prime and 9b+7= square (x^2)

For the prime side of things, you can eliminate a bunch of possible b's.
Most obvious rules for b:
b is an integer.
b is greater than 9 (because you see the digit 9 in the examples)
b is odd (because 6 + an even number gives an even number, hence not a prime)
b cannot be a multiple of 3 (because 6 + a multiple of 3 gives a number divisible by 3, and thus not a prime)
b cannot be 9, 14, 19, 24 etc because numbers in this set when added to 6 give a multiple of 5.
You can repeat this process for 7, 11 etc however beyond 5 it doesn't help very much in terms of gain/effort.

So, possible b's thus far: 11,13,17,23,25,31,35,37,41,43,47,53,61 etc

That's better but it's still a lot of calculation to do on the square side of things....so that's kind of a dead end.

It's also hard to come up with a formula that will predict primes...

However, on the square side of things, you can have a lot more luck.

So we have 9b+7=x^2
solve for b
b=(x^2-7)/9

Is there an easy way to find all the values of x which will yield integers for b?

Yes.

Write the equation another way:
b = (x^2)/9 - 7/9

therefore (x^2)/9 must have a remainder of 7 in order for b to be an integer.

So if you remember the divisor rule of 3s (that if the digits add to a multiple of 3, the original number is a multiple of 3) then you can extend that here.

Side note : the divisor rule is derived as: (example)

486 = 4(100)+8(10)+6(1)
= 4(99+1)+8(9+1)+6
= 4*99+4+8*9+8+6
= 4*99+8*9+4+8+6
The first two terms are definitely divisible by 3, and all that is left is those remainders, and if their sum is divisible by 3 then everything is.

Using that background, we can come up with a similar rule:

let x equal n9+R where n and R are integers, n being the number of multiples of 9 and R being the remainder {1,2,3,4,5,6,7,8}

so:
x^2 = (n9+R)^2
x^2 = (n9+R)(n9+R)
x^2 = (n9)^2 + 2Rn9 + R^2

(n9)^2 is divisible by 9
2Rn9 is divisible by 9

The only thing that really matters then is that last part R^2. If (R^2)/9 equals some whole number plus 7/9, you have basically solved the problem
R = 1 -> 1/9
R = 2 -> 4/9
R = 3 -> 9/9 (1)
R = 4 -> 16/9 (or 1 and 7/9) <----this one
R = 5 -> 25/9 (or 2 and 7/9) <----this one
R = 6 -> 36/9 (4)
R = 7 -> 49/9 (or 5 and 4/9)
R = 8 -> 64/9 (or 7 and 1/9)

So an R of 4 or 5 leads to the desired remainder.

So x can equal n9+4 and n9+5
{13,14,22,23,31,32 etc}

back to b = (x^2-7)/9

plugging into prime equation: b + 6 = (x^2-7)/9 + 6 is a prime

you can either bruteforce from above, or you can do one more step to make it easier:
imagine x is odd:
(odd*odd-odd)/odd+even
(odd-odd)/odd+even
even/odd+even
even+even
even (not prime)

imagine x is even:
(even*even-odd)/odd+even
(even-odd)/odd+even
odd/odd+even
odd+even
odd

therefore, x must be even, leaving {14,22,32 etc} (or basically or start with 14 then +8, +10, +8, +10 etc)

Not much left to test...x is 22, meaning b is 53.

Again, if you have to figure all this stuff out from scratch like I did, then it's faster to bruteforce it. If you have these tricks in your bag already, it's much more feasible.

Please point out any mistakes you find in my reasoning.