Determine the least positive index $x$ such that $4^x − 1$ is divisible by 83.
We need the order of 4 modulo 83, which is the least positive index of 4 congruent to 1 modulo 83.
We note $\gcd(4,83)=1$, so the order exists.
The order is a factor of $\phi(83)=82$. These factors are 1, 2, 41, 82, and these are the only ones we need to test.
The magnitudes grow rapidly large so we need to calculate indirectly, as follows.
Noting that:
- $4^2 \equiv 16 \pmod {83}$
- $16^4 \equiv 49 \pmod {83}$
we have
$$ 4^{41} \equiv (4^2)^20 \times 4 \equiv (16)^20 \times 4 \equiv (16^4)^5 \times 4 \equiv (49)^5 \times 4 \equiv 1129900996 \equiv 1 \pmod {83}$$
So the least positive index $x$ such that $4^x -1$ is divisible by 83 is 41.