+235 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.
+26367 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}\)
