+0  
 
0
64
6
avatar+156 

Find an integer  x such that \(0 \leq x < 527\ \text{and} \ x^{37} \equiv 3 \pmod{527}.\)

Rollingblade  May 28, 2018

Best Answer 

 #4
avatar+19495 
+2

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}\)

 

 

laugh

heureka  May 29, 2018
edited by heureka  May 29, 2018
 #1
avatar+92624 
0

I'd really like to see someone tackle this question.  :/

Melody  May 28, 2018
 #2
avatar
0

x^37 mod 527 = 3, solve for x

Using simple iteration:

x =148. So that:

x =527n + 148, where n =0, 1, 2, 3.....etc.

Guest May 28, 2018
 #3
avatar+92624 
0

That is simple for a computer but I do not think it is how the question was intended to be done.

Melody  May 28, 2018
edited by Melody  May 28, 2018
 #4
avatar+19495 
+2
Best Answer

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}\)

 

 

laugh

heureka  May 29, 2018
edited by heureka  May 29, 2018
 #5
avatar+92624 
+2

Thanks Heureka, that is great    laugh

Melody  May 29, 2018
 #6
avatar+19495 
+2

Thank you, Melody!

 

laugh

heureka  May 29, 2018

4 Online Users

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.