In modulo arithmetic, I thought the modulo had to be a prime number.
It depends upon what you mean by "modulo arithmetic". If the modulus is a
prime number, then you have a field, i.e. division is defined.
For all x and y (with y non-zero), there exists z such that x = y * z,
i.e. z = x / y is always defined. If the modulus isn't a prime number,
then this isn't the case; e.g. 1/2 modulo 2 isn't defined: there is no z
such that 2*z = 1 modulo 2.
But if you just want the result of additions "modulo N" (multiplication
being repeated addition and exponentiation being repeated multiplication),
then all intermediate calculations can be performed modulo N regardless of
whether or not N is prime.
If you calculate in base N (or a base R such that N=R^K for some integer
K), then remember that the carry always propagates from right to left. Any
given digit in the operands can affect that digit in the result, and the
digits to the left of it, but will never affect the digits to the right of
it. So the last K digits of the result will only be affected by the last K
digits of the operands. This holds for addition, multiplication, and for
the base operand of exponentiation, but not for division or the exponent.
This is why, when generating pseudo-random numbers using a linear
congruential generator, you keep the most significant bits and not the
least significant bits (the low bits have short periods as the last N bits
of the output are only affected by the last N bits of the input).
Is there anything special about 171 and 172?
There's nothing particularly special about 172, but Sylvia noted that the
fact 171=900-9^3 can be used to simplify the calculation.
