Find an integer
\(x \)
such that
\(0 \leq x < 527\ \text{and} \ x^{37} \equiv 3 \pmod{527}.\)
0 \leq x < 527\ \text{and} \ x^{37} \equiv 3 \pmod{527}.
\(\begin{array}{|lrcll|} \hline & x^{37} &\equiv& 3 \pmod{527} \\ \text{or}& x^{37} &=& 3 + n\cdot 527 \quad & | \quad 527 = 17\cdot 31 \\ & x^{37} &=& 3 + n\cdot 17\cdot 31 \\\\ \pmod{17}: & x^{37} &\equiv& 3 \pmod{17} \qquad (1) \\ \pmod{31}: & x^{37} &\equiv& 3 \pmod{31} \qquad (2) \\ \hline \end{array}\)
\(\text{By Fermat's Little Theorem $a^{p-1}\equiv1\pmod{p}$ :}\)
\(\begin{array}{|lrcll|} \hline a=x \quad p = 17 : & x^{17-1}\equiv 1\pmod{17} \\ & \mathbf{x^{16}\equiv 1\pmod{17}} \\\\ a=x \quad p = 31 : & x^{31-1}\equiv 1\pmod{31} \\ & \mathbf{x^{30}\equiv 1\pmod{31}} \\ \hline \end{array}\)
\(\text{reduce $x^{37}$ to $x^5$ and $x^7$ :}\)
\(\begin{array}{|rcll|} \hline x^{37} \pmod{17} &\equiv& \underbrace{x^{16}}_{=1}\cdot \underbrace{x^{16}}_{=1}\cdot x^{5} \pmod{17} \quad & | \quad x^{16} \equiv 1\pmod{17} \\ x^{37} \pmod{17} &\equiv& x^{5} \pmod{17} \equiv 3 \pmod{17} \quad & | \quad \text{ see $(1)$ } \\ \mathbf{ x^{5}} & \equiv & \mathbf{ 3 \pmod{17} } \qquad (3) \\ \\ \hline \\ x^{37} \pmod{31} &\equiv& \underbrace{x^{30}}_{=1}\cdot x^{7} \pmod{31} \quad & | \quad x^{30} \equiv 1\pmod{31} \\ x^{37} \pmod{31} &\equiv& x^{7} \pmod{31} \equiv 3 \pmod{31} \quad & | \quad \text{ see $(2)$ } \\ \mathbf{ x^{7} } & \equiv & \mathbf{ 3 \pmod{31} } \qquad (4) \\ \hline \end{array}\)
\(\text{reduce $x^{5}$ to $x$ :} \)
\(\begin{array}{|lrcll|} \hline & x^{16} &\equiv& 1\pmod{17} \quad & | \quad \cdot x \\ & x^{16}x &\equiv& x\pmod{17} \\ & x^{17}&\equiv& x\pmod{17} \quad & | \quad \text{if $17 \pmod{16} \equiv 1 $} \\\\ \text{or} & x^5 &\equiv& 3 \pmod{17} \quad & | \quad \text{raise to the power s } \\ & x^{5s} &\equiv& x \pmod{17} \\ \text{if} & 5s &\equiv& 1 \pmod{16} \\\\ \text{solve }s : & \\ & s &\equiv& 5^{-1} \pmod{16} \\ & s &\equiv& 5^{\phi(16)-1} \pmod{16} \quad & | \quad 5 \text{ and } 16 \text{ are co-prime!} \\ & s &\equiv& 5^{8-1} \pmod{16} \quad & | \quad \phi(16)= 8 \\ & s &\equiv& 5^{7} \pmod{16} \\ & s &\equiv& 13 \pmod{16} \\\\ & x &\equiv& x^{5s} \pmod{17} \\ & &\equiv& x^{5\cdot 13} \pmod{17} \\ & &\equiv& (x^{5})^{13} \pmod{17} \quad & | \quad x^5 \equiv 3 \pmod{17} \\ & &\equiv& 3^{13} \pmod{17} \\ & \mathbf{x} & \mathbf{\equiv}& \mathbf{ 12 \pmod{17} } \\ \hline \end{array}\)
\(\text{reduce $x^{7}$ to $x$ :}\)
\(\begin{array}{|lrcll|} \hline & x^{30} &\equiv& 1\pmod{31} \quad & | \quad \cdot x \\ & x^{30}x &\equiv& x\pmod{31} \\ & x^{31}&\equiv& x\pmod{31} \quad & | \quad \text{if $31 \pmod{30} \equiv 1 $} \\\\ \text{or} & x^7 &\equiv& 3 \pmod{31} \quad & | \quad \text{raise to the power s } \\ & x^{7s} &\equiv& x \pmod{31} \\ \text{if} & 7s &\equiv& 1 \pmod{30} \\ \text{solve }s : & \\ & s &\equiv& 7^{-1} \pmod{30} \\ & s &\equiv& 7^{\phi(30)-1} \pmod{30} \quad & | \quad 7 \text{ and } 30 \text{ are co-prime!} \\ & s &\equiv& 7^{8-1} \pmod{30} \quad & | \quad \phi(30)= 8 \\ & s &\equiv& 7^{7} \pmod{30} \\ & s &\equiv& 13 \pmod{30} \\\\ & x &\equiv& x^{7s} \pmod{31} \\ & &\equiv& x^{7\cdot 13} \pmod{31} \\ & &\equiv& (x^{7})^{13} \pmod{31} \quad & | \quad x^7 \equiv 3 \pmod{31} \\ & &\equiv& 3^{13} \pmod{31} \\ & \mathbf{x} & \mathbf{\equiv}& \mathbf{ 24 \pmod{17} } \\ \hline \end{array}\)
\(\text{finally solve the system for $x$:}\)
\(\begin{array}{|lrcl|rl|rl|} \hline (1) & x &\equiv& 12 \pmod{17} \\ (2) & x &\equiv& 24 \pmod{31} \\ \\ \hline \\ &&& 17 \text{ and } 31 \text{ are co-prime!} \\ & x &=& 12 \cdot 31 \cdot 31^{-1} \pmod{17} & &31^{-1}\pmod{17}& &17^{-1}\pmod{31}\\ & &+& 24 \cdot 17 \cdot 17^{-1} \pmod{31} & \equiv&31^{\phi(17)-1}\pmod{17}& \equiv & 17^{\phi(31)-1}\pmod{31}\\ & &+& 17 \cdot 31 n \qquad n \in Z & \equiv & 31^{16-1}\pmod{17} & \equiv & 17^{30-1}\pmod{31}\\ & & & & \equiv & 31^{15}\pmod{17} & \equiv & 17^{29}\pmod{31}\\ & & & & \equiv & 14^{15}\pmod{17} & \equiv & (17^{2})^{14}\cdot 17\pmod{31}\\ & & & & \equiv & (14^2)^7\cdot 14 \pmod{17} & \equiv & 10^{14}\cdot 17 \pmod{31}\\ & & & & \equiv & 9^7\cdot 14 \pmod{17} & \equiv & (10^2)^{7}\cdot 17 \pmod{31}\\ & & & & \equiv & 11 \pmod{17} & \equiv & 7^{7}\cdot 17 \pmod{31}\\ & & & & & & \equiv & 11 \pmod{31}\\ & x &=& 12\cdot 31 \cdot 11 \\ & &+& 24 \cdot 17 \cdot 11 \\ & &+& 17 \cdot 31 n \\ & x &=& 4092+4488+527n \\ & x &=& \underbrace{8580}_{=148 \pmod {527 }}+527n \\ & x &=& 148 +527n \qquad 0 \leq x < 527 \qquad n=0!\\ & \mathbf{x} & \mathbf{=} & \mathbf{148} \\ \hline \end{array}\)
