Is $41$ a square mod $10^6$?

Question

I'm having trouble with this question, and I was wondering how I would go about solving such problems with high congruences.

I know we cannot use the Legendre symbol to compute this, as $10^6$ is not prime and the Legendre symbol is not multiplicative in its denominator. How would I go about solving problems such as this?

Answer 1

This can be done with complicated algebra.

Think of a number from its decimal structure $X=(x_0x_1x_2x_3x_4x_5)_{(10)}$ there is 6 variables atleast needed to assert the congruence with 1000000.

Squaring X:

$x_0\ x_1\ x_2\ x_3\ x_4\ x_5*\\ x_0\ x_1\ x_2\ x_3\ x_4\ x_5=\\ x_0^2 10^0+\\ 2x_0x_1 10^1+\\ (2x_0x_2+x_1^2) 10^2+\\ (2x_0x_3+2x_1x_2) 10^3+\\ (2x_0x_4+2x_1x_3+x_2^2) 10^4+\\ (2x_0x_5+2x_1x_4+2x_2x_3) 10^5+...$

More digits follow but this is what matters, to locate this number we just need to assign 1,4,0,0,0,0 to the first edges.

$x_0^2 =1 \rightarrow x_0=1\\ 2x_0x_1=4 \rightarrow x_1=2\\ (2x_0x_2+x_1^2)=0 \rightarrow x_2=\{3,8\}\ \text{3 is rejected},c=2\\ (2x_0x_3+2x_1x_2+c)=0 \rightarrow x_3=3, c=4\\ (2x_0x_4+2x_1x_3+x_2^2+c)=0 \rightarrow x_4=0, c=8\\ (2x_0x_5+2x_1x_4+2x_2x_3+c)=0 \rightarrow x_5=5$

We can try now, $(503821)^2=253835600041=41mod10^6$

Answer 2

Hensel lifting gives $$ \begin{align} 1^2&\equiv41\pmod2\\ 1^2&\equiv41\pmod4\\ 1^2&\equiv41\pmod8\\ 5^2&\equiv41\pmod{16}\\ 13^2&\equiv41\pmod{32}\\ 13^2&\equiv41\pmod{64} \end{align} $$ and $$ \begin{align} 1^2&\equiv41\pmod5\\ 21^2&\equiv41\pmod{25}\\ 71^2&\equiv41\pmod{125}\\ 71^2&\equiv41\pmod{625}\\ 696^2&\equiv41\pmod{3125}\\ 696^2&\equiv41\pmod{15625} \end{align} $$ Furthermore, since $(x+32)^2\equiv x^2\pmod{64}$, we get $$ 45^2\equiv41\pmod{64} $$

---

Using the Extended Euclidean Algorithm as implemented in this answer $$ \begin{array}{r} &&244&7&9\\\hline 1&0&1&-7&64\\ 0&1&-244&1709&-15625\\ 15625&64&9&1&0\\ \end{array} $$ says that $$ 1709\cdot64-7\cdot15625=1 $$

---

Thus, since $57\cdot15625=890625$, we have $$ \begin{align} 890625&\equiv1\pmod{64}\\ 890625&\equiv0\pmod{15625} \end{align} $$ and since $1709\cdot64=109376$, we have $$ \begin{align} 109376&\equiv0\pmod{64}\\ 109376&\equiv1\pmod{15625} \end{align} $$ Therefore, since $13\cdot890625+696\cdot109376=87703821$, we have $$ \bbox[5px,border:2px solid #C0A000]{ \begin{align} 703821^2&\equiv41\pmod{1000000}\\ 296179^2&\equiv41\pmod{1000000} \end{align} } $$ Furthermore, since $-13\cdot890625+696\cdot109376=64547571$, we have $$ \bbox[5px,border:2px solid #C0A000]{ \begin{align} 547571^2&\equiv41\pmod{1000000}\\ 452429^2&\equiv41\pmod{1000000} \end{align} } $$ Therefore, since $45\cdot890625+696\cdot109376=116203821$, we have $$ \bbox[5px,border:2px solid #C0A000]{ \begin{align} 203821^2&\equiv41\pmod{1000000}\\ 796179^2&\equiv41\pmod{1000000} \end{align} } $$ Furthermore, since $-45\cdot890625+696\cdot109376=36047571$, we have $$ \bbox[5px,border:2px solid #C0A000]{ \begin{align} 47571^2&\equiv41\pmod{1000000}\\ 952429^2&\equiv41\pmod{1000000} \end{align} } $$