Quadric modular equation

Question

I had to calculate $x$ from $x^2 =x\pmod{10^3}$

I knew that $a = b\pmod{cd} \Rightarrow a=b \pmod c\ \land a=b \pmod d$ when $\gcd(c,d)=1$

Therefore I got two equations :

1. $x^2 = x \pmod 8$
2. $x^2 = x \pmod{125}$

My next step was to go for Chinese remainder but it only got me to $x=x$ and this was not very usefull. What should I do to calculate this $x$ ?

Answer 1

$\pmod{8}$ you can simply test the 8 possible solutions. Or:

$$x^2 \equiv x \pmod{8} \Rightarrow \\ 8 | x(x-1) $$

Now, only one of $x$ and $(x-1)$ is even. Therefore, that one must be divisible by $8$. This implies that $8|x$ or $8|x-1$.

$\pmod{125}$

$$x^2 \equiv x \pmod{125} \Rightarrow \\ 125 | x(x-1) $$

Now, since $x$ and $(x-1)$ are relatively prime, only one of them can be divisible by $5$. This implies that $125|x$ or $125|x-1$.

The Solutions

By the CRT you have 4 solutions, given by the following 4 possibilities. $$ x \equiv 0 \pmod{8,125}$$ $$ x-1 \equiv 0 \pmod{8,125}$$ $$ x \equiv 0 \pmod{8} \mbox { and } x-1 \equiv 0 \pmod{125} $$ $$ x-1 \equiv 0 \pmod{8} \mbox { and } x \equiv 0 \pmod{125} $$

Answer 2

You are right. Let's first solve: $$ x(x-1) \equiv 0 \pmod{8} $$

$x $ and $ x - 1 $. Suppose $ x $ is a solution. If $ x $ is even, let's write $x = 2^kx' $ where $ x' $ is odd ($ k \geq 1 $). Obviously $ x - 1 $ is odd, so the equality is of form: $$ 2^kx'(x-1) \equiv 0 \pmod{8}$$

Obviously, since $x'(x-1) $ is odd, this means that $ k \geq 3 $, so $ x \equiv 0 \pmod{8} $

If $ x $ was odd, the same argument would lead us to the conclusion that $ x - 1 \equiv 0 \pmod 8 $. Now we know that all solutions to the above equation are of form $ 8n $ and $ 8n + 1 $.

So now, let's solve the other one. Suppose that $ x = 8n $: $$ 8n(8n-1) \equiv 0 \pmod{125} $$

$\gcd(8, 125) = 1$, so $ 8 $ is invertible. Its inverse is 47 $$ n(n-47) \equiv 0 \pmod{125}$$

The same argument from before shows that $ n \equiv 0 \pmod{125} $ or $ n \equiv 47 \pmod{125}$. The solutions we get are:

$ x = 8(125m) = 1000m $

$ x = 8(125m + 47) = 1000m + 376$

If we took $ x $ to be of form $ 8n+1 $, we would have got $ n \equiv 0 \pmod{125}$ or $ n \equiv 125-47 \equiv 78 \pmod{125} $. From this case, we get two more solutions:

$ x = 8(125m) + 1 = 1000m + 1 $

$ x = 8(125m + 78) + 1 = 1000m + 625 $