Fermat pseudoprime, base 2

Let m=(4^p-1)/3, where p is a prime larger than 3.  Show that 2^m-1 ≡ 1 (mod m)

Source: BMO 1993 Q2

Solution

Lemma 1: 4^p=1 (mod m).

m=(4^p-1)/3, so 3m=4^p-1, and 4^p=3m+1, so 4^p=1 (mod m).

Lemma 2: 4p|m-1

m=(4^p-1)/3, so m-1=(4^p-4)/3 , so 3(m-1)=4(4^p-1-1)

By Fermat's Little Theorem, 4^p-1=1 (mod p), so p|4^p-1-1.

4p|3(m-1), and 4p and 3 are coprime, so 4p|m-1.

Proof that 2^m-1 = 1 (mod m):

By Lemma 2, a "k" exists such that m-1=4kp, so 2^m-1 = 2^4kp = 4^2kp = (4^p)^2k.

By Lemma 1, 4^p=1 (mod m), so 2^m-1 = (4^p)^2k = 1^2k = 1 (mod m).

Additional Comments

m=(4^p-1)/3 is composite for all prime p larger than 3, because m=(2^p-1)((2^p+1)/3), and both 2^p-1 and (2^p+1)/3 are integers.

So m is a base 2 Fermat pseudoprime.  Since there are infinitely many primes, there are infinitely many base 2 Fermat pseudoprimes.

Internet references

Mathworld: Fermat pseudoprime

Related pages in this website

Number Theory home

Fermat's Little Theorem

 

The webmaster and author of this Math Help site is Graeme McRae.