The Queen of Hearts has just learned that primes of the form

The Queen of Hearts has just learned that primes of the form p 3 (mod 4) have square roots that are easier to compute than the 1 (mod 4) case. Henceforth she declares there no primes of the latter form. When Alice points out that it is hard to ignore p = 5 the Queen reluctantly amends her decree to state that “there are only a finite number of 1 (mod 4) primes”. Mad Hatter was sure this wasn’t correct but was told to accept this as an alternative fact.

He asked the White Rabbit if he knew of a proof in either direction. Rabbit said, “of course, it’s simple.” “Suppose there are only a finite number pk of 1 (mod 4) primes, then consider n = (2p1p2 . . . pk) 2 + 1 and using Fermat that every prime divisor of n is 1 (mod 4) ” “Oh, I’m sorry” says White Rabbit interupting himself, “I’m late for a very important date” as he rushed off. Can you complete his thought?

Solution

Rabbit has nailed it. It is easy to see n 1 (mod 4) and if q is a prime divisor of m2 + 1 with m even then m2 1 (mod q). In this case, (m2 ) (q1)/2 (1)(q1)/2 , but from Fermat, (m2 ) (q1)/2 mq1 1 (mod q). Thus combining these, 1 (1)(q1)/2 so that (q 1)/2 must be even or q 1 (mod 4). However, such a q must equal pj for some j as {p1, . . . pk} was assumed to be the complete listing of 1 (mod 4) primes. But this cannot be, since pj cannot divide n.