+0  
 
0
24
1
avatar+122 

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.

Rollingblade  May 17, 2018
Sort: 

1+0 Answers

 #1
avatar+19376 
+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

 
heureka  May 18, 2018

11 Online Users

avatar
New Privacy Policy (May 2018)
We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  Privacy Policy