Is your answer perfect enough to be a square?

Find a six digit number that is a perfect square such that the number formed by its last three digits is one more than the number formed by its first three digits (for example, 214215 is a number that satisfies this condition, but it is not a perfect square).
(Britain)

Solution

Let the number in question be abcdef. Since abc + 1 = def, we can write the given number as abc x 1000 + def = abc x 1000 + abc + 1 = 1001(abc) + 1. Letting abc = n for the sake of simplicity, the numbers that meet the condition that the number formed by the first three digits is one less than the number formed by the last three digits are of the form 1001n + 1 for some 100 < n ≤ 998 (since n is equal to abc which has to be a three-digit number ⇒ otherwise abcdef will not be a six-digit number). Now, consider the other condition of the problem which expects the number to be a perfect square. So we have the statement 1001n + 1 = x2 for some integer x.

Rearranging and factoring produces

(7 x 11 x 13)n = (x + 1)(x - 1).

We will try to distribute the factors from the left hand side to the right hand side of the equation. In other words, we choose to put 7, 11, 13 and the factors of n into either x+1 or x-1. Since

100000 ≤ x2 ≤ 1000000

316 ≤ x ≤ 1000, 317 ≤ x + 1 ≤ 1001 and 315 ≤ x - 1 ≤ 999.

In order to make the upper bound smaller, we find that if x+1 = 1001 and x-1 = 999, then n = 999 but n ≤ 998 (if abc = n = 999, def = 1000 but def was supposed to be a three-digit number), implying that 317 ≤ x + 1 ≤ 1000 and 315 ≤ x - 1 ≤ 998. (*)

Therefore, we cannot distribute all the factors of 1001 (7, 11, 13) into one of x+1 or x-1 since neither of them can be greater than 1000 as shown in (*). Now, we can consider three cases:

Case 1 : 7, 11 are distributed to the same factor and 13 is put in the other factor.

Case 2 : 7, 13 are distributed to the same factor and 11 is put in the other factor.

Case 3 : 11, 13 are distributed to the same factor and 7 is put in the other factor.

In each of these cases, n has to be composite because 7 x 11 ± 2 ≠ 13p (where p is a prime greater than 100). Therefore, we denote n = ab where a, b ≠ 1. We have to distribute one of these factors to x+1 and the other to x-1.

Now we can choose to proceed with any of the cases to find a six-digit prime that satisfies the conditions of the problem. I will continue with Case 2. If you choose to use a different case and find another answer to this problem, please post your solution in the comments below.

Continuing with the problem, consider that the factors are distributed as follows (you can try other cases as well and you may end up getting another answer):

x+1 = (7 x 13)a = 91a

x-1 = 11b

We exploit a simple relation between these numbers to solve this problem.

91a - 11b = 2

Using the Extended Euclidean Algorithm on this equation since gcd(11, 91) =1 gives

91 = 8(11) + 3

11 = 3(3) + 2

3 = 1(2) + 1

1 = 3 - 1(2)

1 = 3 - 1(11- 3(3))

1= 91 - 11(8) - 11 + 3(91 - 11(8))

1 = 91(4) - 11(33)

2 = 91(8) - 11(66)

Therefore, a = 8 and b = 66 from which we can conclude that n = 8 x 66 = 528.

From the initial equation 1001n + 1, we complete the problem by finding that an answer to this problem is 1001(528) + 1 = 528529.