Having introduced the concept of the (multiplicative) order of a modulo m, let us use it to solve some problems.

Problem 1. Prove that if n > 1 is an integer, then n does not divide 2ⁿ – 1.

Proof. Since n > 1, we can pick the smallest prime factor p of n. Suppose, on the contrary, that n divides 2ⁿ – 1. Then p must also divide 2ⁿ – 1 so we have 2ⁿ ≡ 1 (mod p). On the other hand, since 2ⁿ – 1 is odd, p > 2 so we know by Fermat’s little theorem that 2^p-1 ≡ 1 (mod p). Now if we let d be the multiplicative order of 2 modulo p, then d | n and d | (p-1). This shows that d is a factor of n which is even smaller than p. The only possibility is d = 1, i.e. 2¹ ≡ 1 (mod p) which is absurd. ♦

Problem 2. Prove that if m, n are positive integers with m odd, then 2^m – 1 and 2ⁿ + 1 are coprime.

Proof. Suppose they are not, so there is a prime p which divides both 2^m – 1 and 2ⁿ + 1. Note that p is odd. This means that: 2^m ≡ 1 (mod p) and 2ⁿ ≡ -1 (mod p). But the latter also implies 2²ⁿ ≡ 1 (mod p). Hence, if d is the multiplicative order of 2 modulo p, then d | m and d | 2n but d does not divide n. Thus, d divides 2n but not n, it must be 2k for some k | n. In particular, d is even, which contradicts the fact that d divides odd m. ♦

Problem 3. Prove that if k is a natural number and n = 2^k – 1 then k | φ(n).

Proof. This clearly holds for k = 1. For k > 1, let d = ord_n(2) – which is well-defined since n is odd. By Euler’s theorem, 2^φ(n) ≡ 1 (mod n) so we know that d divides φ(n). On the other hand, since n = 2^k – 1 it’s easy to compute d: the successive powers of 2 modulo n is given by: 1, 2, 2², … , 2^k-1, 2^k ≡ 1 (mod n). Since the first k terms are all < n, it is clear that d = k. Thus, k divides φ(n) as desired. ♦

Here are more problems which can be solved by skilfully applying the concept of order.

Problem 4. Prove that if p is prime, then p^p – 1 has a prime factor which is congruent to 1 mod p.

Problem 5. Prove that if n is even, then any divisor of n⁴ + 1 is congruent to 1 mod 8. Can you generalise the result?

Problem 6. Prove that if n is even and not a multiple of 3, then any divisor of n² + 3 is congruent to 1 mod 3. [ PS. The solution to this problem can be somewhat simplified with quadratic reciprocity, something which I will hopefully cover at a later date. ]

Problem 7. [ IMO 1989 Shortlisted ] Let m > 1 be an integer. Find the smallest positive integer n such that 2¹⁹⁸⁹ divides mⁿ – 1.