Define the sequence an by a1 = 2, an+1 = 2an. Prove that an = an-1 (mod n) for n ≥ 2.
This is easy once you realize that you have to prove a stronger result: an = an-1 (mod m) for all m ≤ n.
We use induction. The result is obviously true for n = 2. Assume it is true for < n, then we must prove that 2an-1 = 2an-2 (mod m), where m ≤ n. If let m = 2r(2s+1). Then 2φ(2r+1) = 1 (mod 2r+1), and since φ(2r+1) < 2r+1 ≤ m ≤ n, we have by induction that an-1 = an-2 (mod φ(2r+1)), and hence 2an-1 = 2an-2 (mod 2r+1). Obviously 2sdivides both 2an-1 and 2an-2, so 2an-1 = 2an-2 (mod 2s). But (2r+1) and 2s are coprime, so 2an-1 = 2an-2 (mod m), as required.
© John Scholes
12 Dec 1998