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* ^{n}* – 1.

**Proof**. Since *n* > 1, we can pick the smallest prime factor *p* of *n*. Suppose, on the contrary, that *n* divides 2* ^{n}* – 1. Then

*p*must also divide 2

*– 1 so we have 2*

^{n}*≡ 1 (mod*

^{n}*p*). On the other hand, since 2

*– 1 is odd,*

^{n}*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}≡ 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.*

^{n}**Proof**. Suppose they are not, so there is a prime *p* which divides both 2* ^{m}* – 1 and 2

*+ 1. Note that*

^{n}*p*is odd. This means that: 2

*≡ 1 (mod*

^{m}*p*) and 2

*≡ -1 (mod*

^{n}*p*). But the latter also implies 2

*≡ 1 (mod*

^{2n}*p*). Hence, if

*d*is the multiplicative order of 2 modulo

*p*, then

*d*|

*m*and

*d*| 2

*n*but

*d*does not divide

*n*. Thus,

*d*divides 2

*n*but not

*n*, it must be 2

*k*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}, … , 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*^{4} + 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*^{2} + 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^{1989} divides *m ^{n}* – 1.

These problems are really hard! 😦

Don’t worry about it. The notes aren’t tagged intermediate for nothing. Just try and see how far you can go. 🙂