- Thread starter
- #1

#### Albert

##### Well-known member

- Jan 25, 2013

- 1,225

y=$x^2$

the last 3 digits of y is also equal to abc

that is y=???abc

please find x and y

- Thread starter Albert
- Start date

- Thread starter
- #1

- Jan 25, 2013

- 1,225

y=$x^2$

the last 3 digits of y is also equal to abc

that is y=???abc

please find x and y

- Jan 26, 2012

- 644

$$x^2 \equiv x \pmod{1000} \tag{1}$$

[JUSTIFY]Clearly for $x$ coprime to $1000$, the only solutions are the trivial $x = 0$ and $x = 1$, so all nontrivial solutions for $x$ must be divisible by either $2$ or $5$, or both. This leaves us with about $600$ possible candidates. Now it should be clear that if a solution works for $1000$, it will also work for $100$, and for $10$. Let's try and find the solutions for $10$:[/JUSTIFY]

$$x^2 \equiv x \pmod{10} \tag{2}$$

[JUSTIFY]We have $5$ potential solutions here, namely $2, 4, 5, 6, 8$ (modulo $10$). Let's check each of them manually, some calculations show that only $5$ and $6$ work. So the solutions must have either $5$ or $6$ as a last digit. Let's now extend our search to $100$, armed with this information (which reduces the set of possible solutions considerably):[/JUSTIFY]

$$x^2 \equiv x \pmod{100} \tag{3}$$

[JUSTIFY]We know from the previous step that the potential solutions are $5, 6, 15, 16, \cdots$. A short exhaustive search tells us that only $25$ and $76$ work. Finally, we have narrowed down the search enough to look for the real solutions:[/JUSTIFY]

$$x^2 \equiv x \pmod{1000} \tag{4}$$

The only possible solutions are $25, 76, 125, 176, \cdots$. Again, trying those 20 potential solutions shows that only $376$ and $625$ work. Therefore, the solutions are $x \in \{ 0, \, 1, \, 376, \, 625 \}$. QED.

[JUSTIFY]This might look like a non-answer given the amount of trial and error involved, but consider that we've only had to try $45$ potential candidates instead of the original $600$, and the cost of this algorithm is asymptotically logarithmic, for instance, finding the solutions with $m = 100000$ would only take $85$ trials, quite efficient.[/JUSTIFY]

Here's an Python 3 script implementing the algorithm outlined above, using recursion, for powers of $10$:

Code:

```
# Work count
work = 0
def Verify(x, m):
global work
work += 1
return pow(x, 2, 10**m) == x
def Solve(m):
# Solutions
found = []
if m == 1:
for x in [2, 4, 5, 6, 8]: # Precomputed
if Verify(x, m):
found.append(x)
return found
possible = Solve(m - 1)
for p in possible:
for x in range(p, 10**m, 10**(m - 1)):
if Verify(x, m):
found.append(x)
return found
def Enumerate(m):
global work
work = 0
found = Solve(m)
# Add trivial solutions
found.append(0)
found.append(1)
found.sort()
print("Solutions are {" + ', '.join(str(x) for x in found) + "}.")
print("Checked " + str(work) + " candidates.")
```

Code:

```
>>> Enumerate(1) # For 10
Solutions are {0, 1, 5, 6}.
Checked 5 candidates.
>>> Enumerate(2) # For 100
Solutions are {0, 1, 25, 76}.
Checked 25 candidates.
>>> Enumerate(3) # For 1000
Solutions are {0, 1, 376, 625}.
Checked 45 candidates.
>>> Enumerate(5) # For 100000
Solutions are {0, 1, 9376, 90625}.
Checked 85 candidates.
>>> Enumerate(8) # For 100000000
Solutions are {0, 1, 12890625, 87109376}.
Checked 145 candidates.
```

So if a better way to do this exists, I'd be interested to see it. It is worth noting that the condition $x^2 \equiv x \pmod{m}$ implies $x^n \equiv x \pmod{m}$ for all $n > 0$, but I could not find how to use this property, sadly.[/JUSTIFY]

- Thread starter
- #3

- Jan 25, 2013

- 1,225

y-x =$x^2-x =x(x-1)$ must be a multiple of 1000

y=$x^2$

the last 3 digits of y is also equal to abc

that is y=???abc

please find x and y

for 1000=$2^3 \times 5^3 =8\times 125$

further more x and (x-1) are coprime

if x is a multiple of 125 then x-1 must be a multiple of 8---------(1)

if x is a multiple of 8 then x-1 must be a multiple of 125---------(2)

so the possible solutions meet restriction of (1) and (2) will be x=376 , and x=625

y=141376=$376^2$ , and 390625=$625^2$

Last edited: