proving that $a\mid b$

I'm trying to prove that $83\mid 3^{123}-1$, or in other words $3^{123}\equiv 1 \mod{83}$ .

Of course $\gcd(83,3)=1$ so from Euler's theorem $3^{\phi(83)}\equiv1 \mod{83}$, and $83$ is prime so $\phi(83)=82$, giving us that $3^{82}\equiv 1 \mod{83}$.

This is where I am stuck. I tried to show that $3^{41} \equiv 1 \mod{83}$ but I couldn't manage to do so. Also $83$ is prime so I can't try to prove this on each of his prime factors separately.

I tried out a few steps up the numbers $3+83k$ to see if there is a nearby square - because if there is such a number $a^2\equiv 3 \bmod 83$, then $3^{41} \equiv a^{82} \equiv 1 \bmod 83$ by Fermat's little theorem.

And luckily, $3+2\cdot 83 =169 = 13^2$. So $13^2\equiv 3$ and $3^{123} \equiv 13^{246}\equiv (13^{82})^3 \overset{\small{FLT}}\equiv 1 \bmod 83$

Another "finding convenient numbers" approach: note that $83+1=84=2^2\cdot3\cdot 7$:

$3^4 = 81\equiv -2$
$3^{32} \equiv 2^8 \equiv 256 \equiv 7$
$\to 3^{41} \equiv 7\cdot(-2)^2\cdot 3 \equiv 84\equiv 1 \bmod 83$

$3^{4}\equiv -2 \mod{83} \Longrightarrow$

$3^{40}\equiv 1024 \mod{83} \Longrightarrow$

$3^{40}\equiv 28 \mod{83}\Longrightarrow$

$3^{41}\equiv 84 \mod{83} \Longrightarrow$

$3^{41}\equiv 1 \mod{83}.$

• +1. Concrete calculation is always the best first approach to a problem. Only get fancy and abstract if that fails. – Wildcard Jan 19 '17 at 22:25
1. See, that:

• $3^4 \equiv (-2) \mod 83$
• $(-2)^8=2^8 \equiv 7 \mod 83$
• $84 \equiv 1 \mod 83$
2. $$3^{123} = (3^4)^{30}3^3 \equiv \left((-2)^{8}\right)^3(-2)^6 3^3 \equiv 7^34^33^3 = 84^3 \equiv 1\mod83$$

Without Euler's Theorem:

$\color\red{3^{4}}\equiv81\equiv\color\red{-2}\pmod{83}\implies$

$3^{123}\equiv3^{4\cdot30+3}\equiv(\color\red{3^{4}})^{30}\cdot3^{3}\equiv(\color\red{-2})^{30}\cdot3^{3}\equiv28991029248\equiv1\pmod{83}$