prove that if n3 mod 4 then n has at least one prime factor

prove that if n3 mod 4 then n has at least one prime factor p3 mod 4

Solution

Assume that p1 = 3, . . . , pn are primes of the form pj 3 mod 4. We will construct a new one by looking at N = 4p1 · · · pn 1 (putting N = 4p1 · · · pn+3 would also work). First, none of the primes pj divides N: note that pj | N +1, so if we had pj | N, then we would have pj | (N +1)N = 1: contradiction. Now we observe that at least one of the prime factors of N has the form p 3 mod 4: in fact, N is odd, hence if such a prime does not exist, then all prime factors of N have the form p 1 mod 4; but then we would have N 1 mod 4 contradicting the construction of N.