residue

[logistic_guy]

here is the question

Suppose that $\displaystyle n = 11021=103 \cdot 107$ and that $\displaystyle x^4 \equiv 1686 ($ mod $\displaystyle 11021)$. Find the least nonnegative residue of $\displaystyle x^2$ modulo $\displaystyle 11021$.


my attemb
i think this question can be solved by legendre symbol $\displaystyle (\frac{a}{p})$
i find
$\displaystyle x^4 \equiv 1686 \equiv 38($ mod $\displaystyle 103)$
$\displaystyle x^4 \equiv 1686 \equiv 81($ mod $\displaystyle 107)$
how to solve these equations?

 

[fresh_42]

$$\begin{array}{lll} x^4-81 &=(x^2-9)(x^2+9)\equiv 0 \pmod{107}\\[6pt] \left(\dfrac{38}{103}\right)&=38^{51}\equiv 1 \pmod{103}\\[6pt] \end{array}$$
That means $38$ is a quadratic residue modulo $103$ and we find the roots $48,55,$ so that

$$\begin{array}{lll} x^4-38 &=(x^2-48)(x^2-55)\equiv 0\pmod{103}\\[6pt] \end{array}$$
Thus
$$\left(107\,|\,(x^2-9)\quad \vee \quad 107\,|\,(x^2+9)\right)\quad \wedge \quad\left(103\,|\,(x^2-48)\quad\vee\quad 103\,|\,(x^2-55)\right)$$and we are looking for a number $a=x^2$ such that
$$a\equiv \pm 9\pmod{107} \text{ AND } \left(a\equiv 48 \pmod{103}\text{ OR }a\equiv 55\pmod{103}\right)$$which leaves us with four possibilities, each of which can be solved (or not) by the Chinese Remainder Theorem.

Chinese Remainder Theorem Calculator - Online Congruence System Solver

Tool to compute congruences with the chinese remainder theorem. The Chinese Remainder Theorem helps to solve congruence equation systems in modular arithmetic.

www.dcode.fr

Spoiler: Solution

1703

 

[logistic_guy]

$$\begin{array}{lll} x^4-81 &=(x^2-9)(x^2+9)\equiv 0 \pmod{107}\\[6pt] \left(\dfrac{38}{103}\right)&=38^{51}\equiv 1 \pmod{103}\\[6pt] \end{array}$$
That means $38$ is a quadratic residue modulo $103$ and we find the roots $48,55,$ so that

$$\begin{array}{lll} x^4-38 &=(x^2-48)(x^2-55)\equiv 0\pmod{103}\\[6pt] \end{array}$$
Thus
$$\left(107\,|\,(x^2-9)\quad \vee \quad 107\,|\,(x^2+9)\right)\quad \wedge \quad\left(103\,|\,(x^2-48)\quad\vee\quad 103\,|\,(x^2-55)\right)$$and we are looking for a number $a=x^2$ such that
$$a\equiv \pm 9\pmod{107} \text{ AND } \left(a\equiv 48 \pmod{103}\text{ OR }a\equiv 55\pmod{103}\right)$$which leaves us with four possibilities, each of which can be solved (or not) by the Chinese Remainder Theorem.

Chinese Remainder Theorem Calculator - Online Congruence System Solver

Tool to compute congruences with the chinese remainder theorem. The Chinese Remainder Theorem helps to solve congruence equation systems in modular arithmetic.

www.dcode.fr

Spoiler: Solution

1703

Thanks professor fresh_42 for the share. I need to analyze this problem further.

 

[fresh_42]

The second line with the Legendre symbol used Euler's identity
$$\left(\dfrac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}.$$I used the Windows calculator to determine the value. To do it manually you could start with $38^2\equiv 2\pmod{103}$ which leads to $$38^{51}=38^{2\cdot 25 +1}=\left(38^2\right)^{25}\cdot 38\equiv 2^{25}\cdot 38=\left(2^8\right)^3\cdot 2\cdot 38\equiv 50^3\cdot 76=125000 \cdot 76 \equiv 61\cdot 76=4636\equiv 1\pmod{103}.$$
In order to find $x^4-38=(x^2-48)\cdot (x^2-55) \pmod{103}$ consider the ansatz $x^4-38=(x^2-a)(x^2-b)=x^4-(a+b)x^2+ab.$ This means we need $a+b \equiv 0\pmod{103}$ and $ab\equiv -38\equiv 65\pmod{103}.$ I used $a+b=103$ and set $ab-65=103 \cdot t .$ That gave me a quadratic polynomial in $a$ with a parameter $t$ after substitution of $b.$ It has two solutions depending on the parameter $t.$ However, we know that $0\le a< 103.$ This condition allows us to find the value of $t$ and finally the two values $a\in \{48,55\}.$

 

[logistic_guy]

Let us share the spoiler.

Are you saying $\displaystyle x^2 \equiv 1703 \ ( \ \text{mod} \ 11021)$ and $\displaystyle 1703$ is the least nonnegative residue of $\displaystyle x^2$?

 

[fresh_42]

Let us share the spoiler.

Are you saying $\displaystyle x^2 \equiv 1703 \ ( \ \text{mod} \ 11021)$ and $\displaystyle 1703$ is the least nonnegative residue of $\displaystyle x^2$?

Yes. If you use the webpage I linked to then you will find the other answers from the equation systems
$$\begin{array}{lll} a\equiv 9 \pmod{107}&\wedge \quad a= 48 \pmod{103}\\ a\equiv 9 \pmod{107}&\wedge \quad a= 55 \pmod{103}\\ a\equiv -9 \pmod{107}&\wedge \quad a= 48 \pmod{103}\\ a\equiv -9 \pmod{107}&\wedge \quad a= 55 \pmod{103}\\ \end{array}$$

 

[logistic_guy]

Yes.

That is very interesting because I did long calculations and got a different answer!

I have used the Chinese remainder theorem and I got at the end:

$\displaystyle x^2 = 227170$ which means

$\displaystyle x^2 \equiv 227170 \ ( \ \text{mod} \ 11021) \equiv 6750 \ ( \ \text{mod} \ 11021)$

So, $\displaystyle 6750$ is the least nonnegative residue of $\displaystyle x^2$

I might share my method someday after fully analyzing it and making sure I did not miss anything.

 

[fresh_42]

That is very interesting because I did long calculations and got a different answer!

I have used the Chinese remainder theorem and I got at the end:

$\displaystyle x^2 = 227170$ which means

$\displaystyle x^2 \equiv 227170 \ ( \ \text{mod} \ 11021) \equiv 6750 \ ( \ \text{mod} \ 11021)$

So, $\displaystyle 6750$ is the least nonnegative residue of $\displaystyle x^2$

I might share my method someday after fully analyzing it and making sure I did not miss anything.

$6750$ is a solution, yes, as is $1703^2=2900209\equiv 1686 \pmod{11021}$ and $1703<6750.$ The other two solutions are $4271$ and $9318.$

 

[logistic_guy]

$6750$ is a solution, yes, as is $1703^2=2900209\equiv 1686 \pmod{11021}$ and $1703<6750.$ The other two solutions are $4271$ and $9318.$

It seems that your method is the way to find the least solution while my method only finds a solution. It is very interesting that you knew your solution was the least and I will indeed study it deeply. Thanks a lot for the share professor.

Am I correct when I assume that this problem has infinite solutions and we have just found $\displaystyle 4$ of them? And the main idea of this exercise is to find only $\displaystyle 1703$?

 

[fresh_42]

It seems that your method is the way to find the least solution while my method only finds a solution. It is very interesting that you knew your solution was the least and I will indeed study it deeply. Thanks a lot for the share professor.

Am I correct when I assume that this problem has infinite solutions and we have just found $\displaystyle 4$ of them? And the main idea of this exercise is to find only $\displaystyle 1703$?

Yes, I think so. If $x\equiv a\pmod{N}$ then all numbers $x=q\cdot N +a$ for all $q\in \mathbb{Z}$ are solutions, so there are always infinitely many of them for modulo equations.