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]

[math]\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}[/math]
That means [imath] 38 [/imath] is a quadratic residue modulo [imath] 103 [/imath] and we find the roots [imath] 48,55, [/imath] so that

[math]\begin{array}{lll} x^4-38 &=(x^2-48)(x^2-55)\equiv 0\pmod{103}\\[6pt] \end{array}[/math]
Thus
[math] \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) [/math]and we are looking for a number [imath] a=x^2 [/imath] such that
[math] a\equiv \pm 9\pmod{107} \text{ AND } \left(a\equiv 48 \pmod{103}\text{ OR }a\equiv 55\pmod{103}\right)[/math]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]

[math]\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}[/math]
That means [imath] 38 [/imath] is a quadratic residue modulo [imath] 103 [/imath] and we find the roots [imath] 48,55, [/imath] so that

[math]\begin{array}{lll} x^4-38 &=(x^2-48)(x^2-55)\equiv 0\pmod{103}\\[6pt] \end{array}[/math]
Thus
[math] \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) [/math]and we are looking for a number [imath] a=x^2 [/imath] such that
[math] a\equiv \pm 9\pmod{107} \text{ AND } \left(a\equiv 48 \pmod{103}\text{ OR }a\equiv 55\pmod{103}\right)[/math]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
[math] \left(\dfrac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}. [/math]I used the Windows calculator to determine the value. To do it manually you could start with [imath] 38^2\equiv 2\pmod{103} [/imath] which leads to [math] 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}. [/math]
In order to find [imath] x^4-38=(x^2-48)\cdot (x^2-55) \pmod{103}[/imath] consider the ansatz [imath] x^4-38=(x^2-a)(x^2-b)=x^4-(a+b)x^2+ab. [/imath] This means we need [imath] a+b \equiv 0\pmod{103}[/imath] and [imath] ab\equiv -38\equiv 65\pmod{103}.[/imath] I used [imath] a+b=103 [/imath] and set [imath] ab-65=103 \cdot t .[/imath] That gave me a quadratic polynomial in [imath] a [/imath] with a parameter [imath] t [/imath] after substitution of [imath] b. [/imath] It has two solutions depending on the parameter [imath] t. [/imath] However, we know that [imath] 0\le a< 103. [/imath] This condition allows us to find the value of [imath] t [/imath] and finally the two values [imath] a\in \{48,55\}. [/imath]

 

[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
[math]\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}[/math]

 

[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.

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

 

[logistic_guy]

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

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 [imath] x\equiv a\pmod{N} [/imath] then all numbers [imath] x=q\cdot N +a [/imath] for all [imath] q\in \mathbb{Z} [/imath] are solutions, so there are always infinitely many of them for modulo equations.