Congruency

Two integers a and b are said to be congruent (mod n), written ab, if a = b + nm for some integer m. For example, 25171 (mod 4). Thus two integers are congruent if they both have the same remainder when divided by n. Mathematically we say a is congruent to b (mod n) if n divides (evenly) into (a-b), and then a and b are in the same residue class.

Solving congruencies is very similar to solving equations. Try to solve the following problems:

1. Find x such that 5x1 (mod 17)

   Click here for a hint
   Click here for the answer

2. Find x such that 5x1 (mod 15)

   Click here for a hint
   Click here for the answer

3. Find x such that 5x1 (mod 14)

   Click here for a hint
   Click here for the answer

These problems are typical of many congruency problems. In the first problem the modulus (17) is prime, and in such cases there is always a solution. In the second problem the modulus (15) is composite and there is no solution, but this is not due to the fact the 15 is not prime. In the third problem the modulus (14) is also composite, but is this case there is a solution. The difference is a result of the following theorem.

If a and n are relatively prime, that is, they have no common factors, then the congruency ax1 (mod n) always has an unique solution.

axb

In number theory, the Euler (pronounced "Oil-er") totient function counts the number of positive integers less than n that are relatively prime to n. For example, if p is prime, then (that is, since p is prime, every positive integer less than p is relatively prime to p.) An interesting result involving the Euler totient function is the following:

This is a generalization of "Fermat's Little Theorem" which states that a ^{p -1}1 mod(p) for any prime p satisfying a < p. If you are interested in the proof of these theorems, see the reference [2]. You should try a few examples to see that it does work out.