We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
304
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+22343 
+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

14 Online Users

avatar
avatar
avatar