Figuring out maths puzzle

KAGY

You may know of the maths puzzle as follows:
there is one 4 digit whole number (n) where the last 4 digits of n^2 are the original number. I'm following it through as follows, but I'm stuck at the last step.

n^2 = 10,000c +n will give me a figure where the last 4 digits are n
so rearranging gives
n(n-1) = 10,000c
the prime factors of 10,000 are 2^4 x 5^4 (I'll write it as 16 x 625 as it's easier to read) so I think I'm right in saying that n must be a multiple of either 16 or 625 (exclusively because n<10,000) and ditto for n-1. So splitting c into a x b we can say that
n = 16a and n-1=625b
so 62<=a<=625 and 2 <= b <= 15

That's where I'm stuck... what's the next step?
BTW I know that the answer is

9376

equivariant

KAGY wrote: »

You may know of the maths puzzle as follows:
there is one 4 digit whole number (n) where the last 4 digits of n^2 are the original number. I'm following it through as follows, but I'm stuck at the last step.

n^2 = 10,000c +n will give me a figure where the last 4 digits are n
so rearranging gives
n(n-1) = 10,000c
the prime factors of 10,000 are 2^4 x 5^4 (I'll write it as 16 x 625 as it's easier to read) so I think I'm right in saying that n must be a multiple of either 16 or 625 (exclusively because n<10,000) and ditto for n-1. So splitting c into a x b we can say that
n = 16a and n-1=625b
so 62<=a<=625 and 2 <= b <= 15

That's where I'm stuck... what's the next step?
BTW I know that the answer is

9376

Nice problem. You made a lot of progress with it.

So we know that [latex] n(n-1) = 16\times 625 \times c [/latex]. Now [latex]n[/latex] and [latex]n-1[/latex] are relatively prime. Therefore, as you point out, either

A) [latex] n = 16 a, n-1=625b[/latex]

or

[latex] n = 625 a, n-1 =16b[/latex]

or
C) [latex] n = 10000 a, n-1 =b[/latex]

or
D) [latex] n= a , n-1 = 10000b [/latex]

You can deal with each of these cases separately. For example in case A)
we have [latex] 16a - 1 = 625b [/latex]. Equivalently,

[latex] 16a -625b = 1[/latex]
To find integer solutions of that equation, use the euclidean algorithm. Same thing should work for all the other cases.

KAGY

equivariant wrote: »

To find integer solutions of that equation, use the euclidean algorithm. Same thing should work for all the other cases.

Thanks, I didn't know about that (I'm better at the applied stuff)
so working with [latex]n=625a [/latex] and [latex] n-1=16b[/latex]

[latex]625a-16b = 1 = 625 - 39\times16[/latex]
so we can say, [latex]a = 1, b=39[/latex]
which gives
[latex]n=625[/latex], and [latex]c = ab = 39[/latex]

back to our original, we have [latex]n^2 = 390,625[/latex]
so it's solved, but only for a three digit number?