+0  
 
0
237
1
avatar+211 

Let $n$ be the inverse of $2\pmod{17}$.

 

That is, let $n$ be the integer $0\leq n < 17$ for which $2n \equiv 1 \pmod{17}$. What is $\left(2^n\right)^2 - 2 \pmod{17}$? Express your answer as an integer from $0$ to $16$, inclusive.

 May 17, 2018
 #1
avatar+21869 
+1

Let $n$ be the inverse of $2\pmod{17}$.

That is, let $n$ be the integer $0\leq n < 17$ for which $2n \equiv 1 \pmod{17}$.
What is $\left(2^n\right)^2 - 2 \pmod{17}$? Express your answer as an integer from $0$ to $16$, inclusive.

 

\(\begin{array}{|rcll|} \hline 2n &\equiv& 1 \pmod {17} \quad & | \quad : 2 \\\\ n &\equiv& \frac12 \pmod {17} \\ \mathbf{n} &\mathbf{\equiv}& \mathbf{ 2^{-1} \pmod {17}} \\ \hline \end{array} \)

 

\(\text{ Solve $2^{-1} \pmod {17}$ }\)

\(\text{Because gcd(2,17)=1 we can continue.}\)

\(\begin{array}{|rcll|} \hline 2^{-1} \pmod {17} &\equiv& 2^{\varphi(17)-1} \pmod {17} \quad & | \quad \varphi(p) = p - 1 \quad \text{$p$ is a prime number} \\\\ && \varphi(17) = 16 \\\\ &\equiv& 2^{16-1} \pmod {17} \\ &\equiv& 2^{15} \pmod {17} \\ &\equiv& 32768 \pmod {17} \\ 2^{-1} \pmod {17}&\equiv& 9 \pmod {17} \\ \mathbf{n} &\mathbf{=}& \mathbf{9} \\ \hline \end{array} \)

 

\(Proof:\\ 2\cdot 9 \equiv 1 \pmod{17} \ \checkmark \)

 

\(\begin{array}{|rcll|} \hline && (2^n)^2 - 2 \pmod{17} \quad & | \quad n = 9 \\ &\equiv& (2^9)^2 - 2 \pmod{17} \\ &\equiv& 2^{18} - 2 \pmod{17} \\ &\equiv& 262144- 2 \pmod{17} \\ &\equiv& 262142 \pmod{17} \\ &\equiv& 2 \pmod{17} \\ \hline \end{array} \)

 

\(\begin{array}{rcll} \mathbf{(2^n)^2 - 2 \pmod{17}} &\mathbf{=}& \mathbf{ 2} \\ \end{array}\)

 

laugh

 May 18, 2018

29 Online Users

avatar
avatar
avatar
avatar