Solution to a puzzle from a few months ago

I never posted a solution to this puzzle, and today one of my students asked me about it.

The puzzle was to find all three-digit numbers that, when multiplied by their successor, give a number concatenated with itself.

So of course when you concatenate a three-digit number x with itself, you get 1001x. So the question becomes: when is k(k+1) a multiple of 1001?

1001 is 7 times 11 times 13. k and k+1 have no prime factors in common, so we have to have that some subset of 7, 11, and 13 are prime factors of k, and the rest are prime factors of k + 1. Furthermore these are going to be proper subsets; if we have that 7, 11, and 13 are prime factors of k and none of those are prime factors of k+1, or vice versa, then we get that k doesn't in fact have three digits.

So we can have the following six situations:

(1) k is a multiple of 7 and k + 1 is a multiple of 143;

(2) k is a multiple of 11 and k + 1 is a multiple of 91;

(3) k is a multiple of 13 and k + 1 is a multiple of 77;

(4) k is a multiple of 77 and k + 1 is a multiple of 13;

(5) k is a multiple of 91 and k + 1 is a multiple of 11;

(6) k is a multiple of 143 and k + 1 is a multiple of 7.

In each case we can then use the Chinese remainder theorem to find k. Let's consider the first case: we have that k ≡ 0 (mod 7), k ≡ -1 (mod 11), k ≡ -1 (mod 13).

The CRT tells us that the solution to the system of congruences

k ≡ a₇ (mod 7), k ≡ a₁₁ (mod 11), k ≡ a₁₃ (mod 13)

is

k ≡ a₇(143)(143^-1)₇ + a₁₁(91)(91^-1)₁₁ + a₁₃ (77)(77^-1)₁₃ (mod 1001)

where I'm using (a^-1)_b to stand for the inverse of a mod b. The other solutions differ from this by multiples of 1001. We can find the inverses by brute force:

(143^-1)₇ = (3^-1)₇ = 5, (91^-1)₁₁ = (3^-1)₁₁ = 4, (77^-1)₁₃ = (12^-1)₁₃ = 12.

So we finally get

k ≡ 715 a₇ + 364 a₁₁ + 924 a₁₃ (mod 1001).

Now, the case (1) corresponds to a₇ = 0, a₁₁ = -1, a₁₃ = -1; so we get

k ≡ 0 - 364 - 924 (mod 1001)

and so we get the solution k = -364 - 924 + (2)(1001) = 714. Indeed (714)(715) = 510510. (714 and 715 are a Ruth-Aaron pair.) The other five situations lead to, respectively, k = 363, 923, 77, 637, 286 and k(k+1) = 132132, 852852, 6006, 406406, 82082.