2
$\begingroup$

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?

  • 1
    @ArturoMagidin: That's fair. I could have gone either way, but I agree.2012-01-13

1 Answers 1

3

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.