Sorry for my English, it's not my first language and that's a lot more evident when we talk about math.

I'm currently taking a cryptography class in university and we have to deal with very big mod numbers, I'm familiar with using Fermat and Euler to deal with large exponents on things like $$6^{219} \pmod{35}$$ But now I'm trying to deal with smaller numbers, and I just can't seem to find a way out, for example, lets say: $$19^3 \pmod{55}$$ Is there a quick way to solve smaller cases like this? Sure I could easily go through the math, but on a very large exam on a very tight timer, I would like to minimize my number crunching time, I'm just wondering, is there a theorem or anything of the sorts to sort stuff like this?

  • $\begingroup$ Very related (and possibly a duplicate): math.stackexchange.com/questions/36318/… $\endgroup$ – JavaMan Jan 13 '12 at 16:33
  • 1
    $\begingroup$ @JavaMan: I don't think it's really a duplicate: here Joao is asking for minimizing computation with small exponents; repeated squaring here would not help, since you would end up having to compute $19^2$ and then multiplying the result by $19$, which means you are just computing $19^3$. $\endgroup$ – Arturo Magidin Jan 13 '12 at 16:36
  • 1
    $\begingroup$ @ArturoMagidin: That's fair. I could have gone either way, but I agree. $\endgroup$ – JavaMan Jan 13 '12 at 16:40

For composite moduli divisible by more than one prime, you can use the Chinese Remainder Theorem:

To compute $19^3\bmod 55$ it suffices to compute $19^3\bmod 5$ and $19^3\bmod 11$. Since $19\equiv 4\equiv -1\pmod 5$, we have $19^3\equiv -1\pmod{5}$. Since $19\equiv 8\equiv -3 \pmod{11}$, then $19^3 \equiv -27\equiv -5\equiv 6\pmod{11}$.

So you are looking for an integer that is $-1\bmod 5$ and $6\bmod 11$. This quickly leads to $39$ (by inspection), so $19^3\equiv 39\bmod{55}$.

(To solve it algebraically, note that you are looking for $x\equiv 4\pmod{5}$, hence $x=4+5k$; since $x\equiv 6\pmod{11}$, we have $4+5k\equiv 6\pmod{11}$, or $5k\equiv 2\pmod{11}$, $10k\equiv 4\pmod{11}$, $-k\equiv 4\pmod{11}$, so $k\equiv 7\pmod{11}$. Plugging into $x$ we get $x = 4 + 5(7+11m) = 39+55m$, so $x\equiv 39\pmod{55}$.)

If your modulus is a prime power, though, I suspect you'll have to just crunch a bit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.