There are many tricks that you can do to make modular arithmetic easier. For example, suppose you want to know what 1234567890 mod 17 is, but you don't have a numeric type big enough to represent 1234567890. Well, what do we know about %
, assuming all numbers are positive?
(a+b)%e == ((a%e)+(b%e))%e
(c*d)%e == ((c%e)*(d%e))%e
If you don't understand why these identities are true, go back to the definition of %
and study them until you have this solid.
Now that we know that, we know that
1234567890 % 17 = (12345 * 100000 + 67890) % 17
= ((((12345 % 17) * (100000 % 17)) % 17) + (67890 % 17)) % 17
And now you have only much smaller numbers. If those numbers are still too big, keep breaking them down until they're small enough.
I answered a very similar question on the Math StackExchange site; it might also be of help to you.
https://math.stackexchange.com/questions/91583/implementing-fermats-primality-test/91584#91584