Next: Primitive roots Up: Introduction to Number Theory Previous: The Greatest Common Divisor   Contents

## Powers modulo a prime

The sequence

has many applications in cryptography. Before looking at theoretical properties, the example below (done using a pocket calculator) should make clear that it is practical to compute these numbers, even when many digits are involved.

Suppose we want to compute  mod 987. The basic trick is to start with a number and keep squaring:

Since ,

Calculations with exponents involve not-too-many multiplications. If the numbers have several hundred digits, however, it is necessary to design special subroutines to do the multiplications (see Knuth, volume 2).

Let us look at the sequence of powers of 2 mod 11:

Each number from 1 to 10 appears in the sequence.

Theorem 5   Let be a prime. There is an such that for every , there is such that .

It is not always the case that . The powers of 2 mod 7 are 2, 4, 1 after which the sequence repeats and we never get 3, 5, or 6.

The proof of Theorem 5 is long, and we will give it in section 2.5. For now, we want to look at some of its consequences.

Corollary 6   Let be as in Theorem 5. Then .

Proof: We know that for some . If , the sequence of powers of would start repeating before we got all the numbers: , , etc. height 8pt width 4pt

Corollary 7   For any , .

Proof: Let be as in Theorem 5. Using Corollary 6

Corollary 8   If , then

Proof: For some integer , and by Corollary 7

Lemma 9   Let , the smallest positive number such that . Then for any with divides evenly. In particular, by Corollary 7, divides evenly.

Proof: If does not divide , then for some , but

would contradict the definition of . height 8pt width 4pt

Next: Primitive roots Up: Introduction to Number Theory Previous: The Greatest Common Divisor   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14