Question 12 Marks
Prove that: 3500 ≡ 2 (mod 7)
Answer
View full question & answer→In order to prove $3^{500} \equiv 2(\bmod 7)$, let us first find an integer $k$ such that $3^k \equiv \pm 1(\bmod 7)$.
We know that $3^1 \equiv 3(\bmod 7)$
$
\begin{array}{l}
\Rightarrow 3^2 \equiv 3 \times 3=9 \equiv 2(\bmod 7) \\
\Rightarrow 3^3 \equiv 3 \times 2(\bmod 7) \\
\Rightarrow 3^3 \equiv 6 \equiv-1(\bmod 7)
\end{array}
$
Thus, we find that $3^3 \equiv-1(\bmod 7)$. Let us now express $3^{500}$ in terms of $3^3$.
$
3^{500}=\left(3^3\right)^{166} \times 3^2
$
Now,
$3^3 \equiv-1(\bmod 7)$
$\Rightarrow\left(3^3\right)^{166} \equiv(-1)^{166}(\bmod 7)\left[\because a \equiv b(\bmod m) \Rightarrow a^n \equiv b^n(\bmod m)\right]$
$\Rightarrow\left(3^3\right)^{166} \times 3^2 \equiv(-1)^{166} \times 3^2(\bmod 7)[\because a \equiv b(\bmod m) \Rightarrow a x \equiv b x(\bmod m)]$
$\Rightarrow 3^{500} \equiv 9(\bmod 7)$
But, $9 \equiv 2(\bmod 7)$. Thus, we obtain
$
\begin{array}{l}
3^{500} \equiv 9(\bmod 7) \text { and } 9 \equiv 2(\bmod 7) \\
\Rightarrow 3^{500} \equiv 2(\bmod 7)[\because a \equiv b(\bmod m), b \equiv c(\bmod m) \Rightarrow a \equiv c(\bmod m)]
\end{array}
$
We know that $3^1 \equiv 3(\bmod 7)$
$
\begin{array}{l}
\Rightarrow 3^2 \equiv 3 \times 3=9 \equiv 2(\bmod 7) \\
\Rightarrow 3^3 \equiv 3 \times 2(\bmod 7) \\
\Rightarrow 3^3 \equiv 6 \equiv-1(\bmod 7)
\end{array}
$
Thus, we find that $3^3 \equiv-1(\bmod 7)$. Let us now express $3^{500}$ in terms of $3^3$.
$
3^{500}=\left(3^3\right)^{166} \times 3^2
$
Now,
$3^3 \equiv-1(\bmod 7)$
$\Rightarrow\left(3^3\right)^{166} \equiv(-1)^{166}(\bmod 7)\left[\because a \equiv b(\bmod m) \Rightarrow a^n \equiv b^n(\bmod m)\right]$
$\Rightarrow\left(3^3\right)^{166} \times 3^2 \equiv(-1)^{166} \times 3^2(\bmod 7)[\because a \equiv b(\bmod m) \Rightarrow a x \equiv b x(\bmod m)]$
$\Rightarrow 3^{500} \equiv 9(\bmod 7)$
But, $9 \equiv 2(\bmod 7)$. Thus, we obtain
$
\begin{array}{l}
3^{500} \equiv 9(\bmod 7) \text { and } 9 \equiv 2(\bmod 7) \\
\Rightarrow 3^{500} \equiv 2(\bmod 7)[\because a \equiv b(\bmod m), b \equiv c(\bmod m) \Rightarrow a \equiv c(\bmod m)]
\end{array}
$