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$
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}$