+0

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

0
304
1
+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
+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}$$

May 18, 2018