The inverse of 3 modulo 7 is ________.

Step 1 (Modular Inverse Definition): The modular inverse of $a$ modulo $m$ is an integer $x$ such that:

Here, we need to find $x$ such that $3x\equiv 1(\mathrm{mod}7)$.

Step 2 (Testing Candidate Residues): We test residues in the ring ${\mathbb{Z}}_7=\{0,1,2,3,4,5,6\}$:

• $3\times 0=0\not\equiv 1(\mathrm{mod}7)$

• $3\times 1=3\not\equiv 1(\mathrm{mod}7)$

• $3\times 2=6\not\equiv 1(\mathrm{mod}7)$

• $3\times 3=9\equiv 2\not\equiv 1(\mathrm{mod}7)$

• $3\times 4=12\equiv 5\not\equiv 1(\mathrm{mod}7)$

• $3\times 5=15=2\times 7+1\equiv 1(\mathrm{mod}7)$

Step 3 (Conclusion): Since $3\times 5\equiv 1(\mathrm{mod}7)$, the modular inverse of 3 modulo 7 is exactly 5.