Order of an Element Modulo m and Applications – Part II

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 2n – 1.

Proof. Since n > 1, we can pick the smallest prime factor p of n. Suppose, on the contrary, that n divides 2n – 1. Then p must also divide 2n – 1 so we have 2n ≡ 1 (mod p). On the other hand, since 2n – 1 is odd, p > 2 so we know by Fermat’s little theorem that 2p-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. 21 ≡ 1 (mod p) which is absurd. ♦

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

Proof. Suppose they are not, so there is a prime p which divides both 2m – 1 and 2n + 1. Note that p is odd. This means that: 2m ≡ 1 (mod p) and 2n ≡ -1 (mod p). But the latter also implies 22n ≡ 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 = 2k – 1 then k | φ(n).

Proof. This clearly holds for k = 1. For k > 1, let d = ordn(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 = 2k – 1 it’s easy to compute d: the successive powers of 2 modulo n is given by: 1, 2, 22, … , 2k-1, 2k ≡ 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 pp – 1 has a prime factor which is congruent to 1 mod p.

Problem 5. Prove that if n is even, then any divisor of n4 + 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 n2 + 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 21989 divides mn – 1.

This entry was posted in Notes and tagged , , . Bookmark the permalink.

2 Responses to Order of an Element Modulo m and Applications – Part II

  1. Eugene Lee says:

    These problems are really hard! 😦

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s