Ask Uncle Colin: A Modulo Mistake

Ask Uncle Colin is a chance to ask your burning, possibly embarrassing, maths questions -- and to show off your skills at coming up with clever acronyms. Send your questions to colin@flyingcoloursmaths.co.uk and Uncle Colin will do what he can.

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 remainder1. 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

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. although I suspect that's what MATLAB is trying to do here []

Share

3 comments on “Ask Uncle Colin: A Modulo Mistake

  • Mark Ritchings

    The Euler-Fermat theorem also provides a quick method. $a^{\phi (m) } \equiv 1 \pmod m$ so in this case we have $3^{12} \equiv 1 \pmod {13}$.

    You might also like to try 12345678901235 – 12345678901234 on a calculator.

    [Colin’s note: $\phi(m)$ is Euler’s totient function, the number of positive integers below $m$ that are relatively prime to it. Since 13 is prime, everything between 1 and 12 is co-prime with it, so $\phi(13)=12$. For any prime $p$, $\phi(p) = p-1$.]

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter