[RESOLVED] Modulus of gigantic powers: howwww?

[Mavrisa]

This is more of a mathematics question but I didn't see a math forum, so I picked this one.

I was at a programming competition today and one of the problems required you to find the modulus of rather large numbers and place them in an array. the numbers were:

x^1, x^2, x^3, ... x^n.

where x is some term (between 1 and 28) and n could be as large as 249.

Then you have to get the modulus (divisor being 29) of each, so the number datatype was not nearly enough to hold it (in order to have it return an integer)

Needless to say, our team didn't do very well, but I have no idea how the successful teams did it.

I found that for a modulus of 29 (or all odd numbers, m), numbers repeat every 28 terms (m-1, so long as the base is not also m). But that still means that I could possibly be calculating 28^28, or 3.3145523113253374862572728253365e+40, which, still, is not representable as an integer.

Is there any way that I could do a simple calculation to find the first 28 terms? I have looked all over and haven't found a solution.

Thank you very much to anyone who can help even a bit,
Mavrisa.

[sstalder]

Moved to Math and Physics.

[Mavrisa]

Ah my bad :P
But resolved, thanks, once again, to wikipedia.