By adding 1 to the non leading zeros number N = AAABBBCCC, it becomes a square. Find N.
A, B, and C are different digits.
Note: While a solution is trivial with the aid of a computer program, show how to derive it without one.
N = 111,999,888 is the unique solution to the given problem.
EXPLANATION:
Let N + 1 = M^2 (say), whenever M is a positive integer. Then M^2 - 1 = AAABBBCCC, so that (M^2 - 1) is divisible by 111, so that M is indivisible by 3.
Now, C= 0, 3, 4, 5, 8, 9 are the only possibilites.
For C= 3, the last 3 digits of M^2 is 334, which is an even number which is not divisible by 4. Contradiction.
For C= 4, the last 2 digits of M^2 is 45, so M^2 cannot be a perfect square.
If C=9, then the last three digits of M^2 are all zero, but the fourth digit from the right is non zero, which is a contradiction, since M^2 must contain an even number of zeroes.
Thus, the last three digits of M^2 must be 001, 556, or 889.
Now, if k is the minimum positive integer such that, M^2(mod 1000) = k^2, then it can be easily shown that:
M = (250*j +/- k), where j is a nonnegative integer, and j is even whenever k is even, with no restriction on k if j is odd.
......(i)
Recalling that M^2 (Mod 111) = 1, it follows that:
M (mod 37) = +/-1, and M is indivisible by 3. ........(ii)
Accordingly, (250*j +/- k) (mod 37) = +/-1, gives:
(-9j +/- k) (mod 37) = +/- 1 .........(iii)
Also, 250(j+1) > 10^4, and: 250j< sqrt(10^9), so that:
39< j < 126 .........(iv)
Case (1): Last three digits of M^2 is 001
This is possible iff k=1, so that:
(-9j +/- 1) (mod 37) = +/- 1
Now, (9j+1,9j-1)(mod 37) = (1, -1) gives:
j (mod 37) = 0, so that the valid values of j satisfying (iii) are j = 74, 111, so that:
M = (250*74 +/- 1, 250*111 +/- 1)
= 18499, 27751 (since 18501 and 27749 are divisible by 3)
It may easily be verified that none of these two values yield the desired structure for M^2.
Also, (9j+1,9j-1)(mod 37) = (-1, 1) gives:
j (mod 37) = +/- 8.
Accordingly, j = 45, 82, 119 .... (a)
AND, (B) j = 66, 103 ......(B)
Thus, M = (250*45 + 1), (250*82 + 1), (250*66-1) since j = 119 and 103 yields M's that are divisible by 3.
or, M = 11251, 20501, or 16499.
None of these three values yield the desired structure for M^2.
Case (2) : Last three digits of M^2 is 556
Obviously 556 is even, so that k will be even, and so j must be even.
Clearly, the last digit of k is 4, or 6, and a liitle trial and error establishes that 166^2 = 27,556, so that k = 166
Accordingly, (-9j +/- 166) (mod 37) = +/- 1
or, (-9j +/- 18) (mod 37) = +/- 1
or, (a):j (mod 37) = 6, -2 for (-9j + 18) (mod 37) = +/- 1, and:
(b):j (mod 37) = 2, -6 for (-9j - 18) (mod 37) = +/- 1
Thus, j = 80, 72 for (a) and:
j = 76, 68 for (b)
Now, j = 80 is discounted, since these would yield M that is divisible by 3.
It may be verified that the other three values do not yield the desired structure for M^2.
Case (3): Last three digits are 889
Since k is odd, there is no restriction on j, and by trial and error, 83^2 = 6,889, so that: k = 83
Hence, (-9j +/- 83) (mod 37) = +/-1
or, (j +/- 1) (mod 37) = +/- 4
or, j (mod 37)
= 5, -3 whenever (-9j + 83) (mod 37) = +/- 1,...(a), and:
= -5, 3 whenever (-9j - 83) (mod 37) = +/- 1...(b)
Thus, j = 42, 79, 116, 71, 108, for (a) and:
j = 69, 106, 40, 77, 114 for (b)
j = 79 and 77 are discounted as these would yield M's that are divisible by 3.
For j= 42, we obtain:
M = 250*42 + 83 = 15083, giving:
M^2 = 111,999,889, so that:
(M^2-1) = 111,999,888
It can easily be verified that none of the remaining six values yield the desired structure for M^2.
Accordingly, N = 111,999,889 - 1 = 111,999,888, and:
Consequently, N = 111,999,888 is the unique solution to the given problem.
Note:
It is trivially apparent that assuming M to be a negative integer would have led to the same value of M^2, and therefore the same solution.
Edited on July 17, 2008, 11:38 am
Analytic Solution
