Dear Uncle Colin,
I wanted to work out $3^{41}\mod 13$: Wolfram|Alpha says it’s 9, but MATLAB says it’s 8. They can’t both be right! What gives?

MATLAB Obviously Doesn’t Understand Logical Operations

Hi, MODULO! First up, when computers disagree, the best thing to do is check by hand. Luckily, you don’t have to work out $3^{41}$ by hand and then divide it by 13 to find the remainder ((although I suspect that’s what MATLAB is trying to do here)). Instead, there’s a quicker way and a much quicker way.

The quicker way first: you can start from $3^0 = 1$ and continually multiply by 3, casting out 13s, until you reach $3^{41} \mod 13$: it starts (all the following modulo 13) $3^1 \equiv 3$; $3^2 \equiv 9$; $3^3 \equiv 1$; $3^4 \equiv 3$; $3^5 \equiv 9$; $3^6 \equiv 1$; … $3^{40} \equiv 3$ and $3^{41} \equiv 9 \mod 13$, as Wolfram|Alpha says.

You might have spotted a pattern as you went through there: the modulos very quickly fell into a cycle of period 3. If you’re sharp, you can spot that $3^{39} \mod 13 = (3^3)^{13} \equiv 1 \mod 13$, meaning $3^{41} = 3^{39} \times 3^{2} \equiv 9 \mod 13$.

The bigger question, though, is ‘why does MATLAB get it wrong?’. The reason turns out to be the way MATLAB stores numbers. While many languages, when they see an integer, treat it as an integer of arbitrary size, MATLAB sees it as a floating-point number, which has an accuracy of 52 bits. That is, it can only express floating-point numbers accurately if they’re smaller than $2^{52} ~ 4.5 \times 10^{15}$. That’s between $3^{33}$ and $3^{34}$, so $3^{41}$ gets messed up because it’s too big for MATLAB to store sensibly.

-- Uncle Colin