ABSTRACT
In this chapter we are going to see some further results about congruence of integers. Most of these are to do with working out the congruence of large powers of an integer modulo some given integer m. I showed you some ways of tackling this kind of question in the last chapter (see Examples 13.2 and 13.3). The first result of this chapter — Fermat’s Little Theorem — is a general fact that makes powers rather easy to calculate when m is a prime number. The rest of the chapter consists mainly of applications of this theorem to solving some special types of congruence equations modulo a prime or a product of two primes, and also to the problem of finding large prime numbers using a computer. We’ll make heavy use of all this material in the next chapter on secret codes.
