Table of Contents
|
The Order of a (mod m)
Recall that by Euler's theorem that if $(a, m) = 1$, then $a^{\phi (m)} \equiv 1 \pmod {m}$. However, we will now be interested in the congruence $a^t \equiv 1 \pmod {m}$ for $1 ≤ t ≤ \phi (m)$. The smallest such positive t that satisfies this congruence is called the order of a (mod m) or alternatively the exponent to which a belongs (mod m).
Notice that if $(a, m) = 1$, then the least residues of the integers $a, a^2, a^3, ...$ (mod m) are all relatively prime to m. We know that there are $\phi (m)$ least residues that are relatively prime to m, but there are infinitely many powers of a. Hence it follows that for some j ≠ k and j > k then:
(1)Since $(a, m) = 1$, it thus follows that we can divide both sides by a^k to obtain:
(2)In fact there are infinitely many powers of a that satisfy this congruence. For example since $a^{t + k\phi (m)} = a^t (a^k)^{\phi m}$, then for any positive integer k:
(3)Let's create a table for $a^n \mod {13}$. We will let a = 1, a = 2, …, a = 12, and calculate a (mod m), a2 (mod m), …, a^12 (mod m).
a | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 4 | 8 | 3 | 6 | 12 | 11 | 9 | 5 | 10 | 7 | 1 |
3 | 9 | 1 | 3 | 9 | 1 | 3 | 9 | 1 | 3 | 9 | 1 |
4 | 3 | 12 | 9 | 10 | 1 | 4 | 3 | 12 | 9 | 10 | 1 |
5 | 12 | 8 | 1 | 5 | 12 | 8 | 1 | 5 | 12 | 8 | 1 |
6 | 10 | 8 | 9 | 2 | 12 | 7 | 3 | 5 | 4 | 11 | 1 |
7 | 10 | 5 | 9 | 11 | 12 | 6 | 3 | 8 | 4 | 2 | 1 |
8 | 12 | 5 | 1 | 8 | 12 | 5 | 1 | 8 | 12 | 5 | 1 |
9 | 3 | 1 | 9 | 3 | 1 | 9 | 3 | 1 | 9 | 3 | 1 |
10 | 9 | 12 | 3 | 4 | 1 | 10 | 9 | 12 | 3 | 4 | 1 |
11 | 4 | 5 | 3 | 7 | 12 | 2 | 9 | 8 | 10 | 6 | 1 |
12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 |
a | Order of a (mod 13) |
---|---|
1 | 1 |
12 | 2 |
3, 9 | 3 |
5, 8 | 4 |
4, 10 | 6 |
2, 6, 7, 11 | 12 |
Notice that the only possible orders for a are 1, 2, 3, 4, 6, and 12. Interestingly enough, these are all divisors of 12. So how is 12 related to 13? Well we know that 13 is a prime, so $\phi (13) = 12$.
Theorem 1: If (a, m) = 1 and a has order t (mod m), then an ≡ 1 (mod m) if and only if n is a multiple of t.
- Proof: Suppose that $n = tq$, that is, n is a multiple of t. It thus follows that $a^n \equiv a^{tq} \equiv (a^t)^q \equiv (1)^q \equiv 1 \pmod m$. Hence if $a^n \equiv 1 \pmod m$, then n must be a multiple of t.
- Proof (Converse): Suppose that $a^n \equiv 1 \pmod m$. Since t is the order of a (mod m), n ≥ t. Hence we can rewrite n as $n = qt + r$ by the division algorithm. We thus obtain that: $a^n \equiv a^{qt + r} \equiv (a^t)^qa^r \equiv (1)^q a^r \equiv a^r \pmod m$. But r = 0 since 0 ≤ r < t since the order of a (mod m) is t. Hence n = qt.
Theorem 2: If (a, m) = 1 and a has order t (mod m), then t | Φ(m).
- Proof: We know that from theorem 1 that $\phi (m)$ must be a multiple of t since by Euler's theorem $a^{\phi (m)} \equiv 1 \pmod m$. Hence t | Φ(m).
We can verify from the original example that all of the orders of a (mod 13) were 1, 2, 3, 4, 6, and 12. All of these divide $\phi (13) = 12$. 1 | 12, 2 | 12, 3 | 12, 4 | 12, 6 | 12, and 12 | 12.
Theorem 3: If p and q are both odd primes, and q | ap - 1, then either q | a - 1 or q = 2kp + 1.
- Proof: By the definition of a congruence, we know that $a^p \equiv 1 \pmod q$ since q | ap - 1. The order of a (mod q) must be a divisor of p by theorem 1, but there are only two divisors of p, namely 1 and p. Suppose that the order of a (mod q) is 1. Hence $a^1 \equiv 1 \pmod q$, so then q | a - 1. Suppose that the order of a (mod q) is p. By theorem 2, p must divided $\phi (q) = q - 1$. Hence p | q - 1, or rather $np = q - 1$ or $q = np + 1$. The lefthand side of this equation is odd, hence, the righthand side of this equation must also be odd. Since p is an odd prime and 1 is odd, then n must be even. Hence n = 2k for k ≥ 1. Hence $q = 2kp + 1$.
Example 1
Verify theorem 3 with q = 3 and a = 4, and p = 5.
We must first verify that q | ap - 1. In fact, this is true. 3 | 45 - 1, or rather 3 | 1023. So either 3 | 4 - 1 or 3 = 2k(5) + 1. Clearly 3 | 3, so this is true, and 3 = 10k + 1 does not work since $k \in \mathbb{Z}$ and 10k + 1 > 3.
Theorem 4: If t is the order of a (mod m), then ar ≡ as (mod m) if and only if r ≡ s (mod t).
- Proof: Suppose that r ≥ s. Hence with the congruence $a^r \equiv a^s \pmod m$, then $a^{r-s} \equiv 1 \pmod m$. We know that t is the order of a (mod m). By theorem 1, r-s must be a multiple of t, that is t | r - s. Hence $r \equiv s \pmod t$.