Ask Uncle Colin: A Modulo Mistake

Dear Uncle Colin,
I wanted to work out $3^{41}\mathrm{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 ¹. 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}\mathrm{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\mathrm{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}\mathrm{mod}13=(3^3{)}^{13}\equiv 1\mathrm{mod}13$, meaning $3^{41}=3^{39}\times 3^2\equiv 9\mathrm{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

Footnotes:

1. although I suspect that’s what MATLAB is trying to do here