# Infinitely many primes $\equiv 3 \mod 4$

Question 1 Is the following proof of the infinitude of primes $\equiv 1\mod 4$ okay?

Consider a prime divisor $p\mid (n!)^2+1$. Then $(n!)^2\equiv -1 \mod p$, hence $n!$ has multiplicative order $4$ in $\Bbb F_p^\times$ (question: is this conclusion true? what did I use here?).

Thus $n!\in \Bbb F_p^\times$ generates a subgroup of order $4$ and by Lagrange, $4\mid p-1$, i.e. $p\equiv 1\mod 4$.

Now we do the same thing, replacing $n$ by $p$. This will give a new prime $\equiv 1\mod 4$ and this prime is bigger than $p$ (otherwise it would divide $1$).

Question 2 My lecture notes say that from this one can conclude that there are infinitely many primes $p\equiv 3\mod 4$ by considering $n!-1$, which leaves remainder $3$ upon division by $4$. How does this imply infinitude of such primes?

• I don't understand what you used in Question 1; your argument is certainly not true. The only possible orders $-1$ can have modulo a prime are $1$ and $2$. – darij grinberg Jul 23 '16 at 14:55
• Sorry I meant $n!$ has multiplicative order $4$. I edited it. – MyNameIs Jul 23 '16 at 14:59

The notes means that, for $n\geq 4$, $n!-1$ has remainder $3$ modulo $4$. It cannot have any prime factor $p\leq n$. It also must have a prime factor $p\equiv 3\pmod 4$ because if $N=p_1p_2\dots p_k$ and $p_i\equiv 1\pmod 4$ then $N\equiv 1\pmod 4$.

So given any $n$, there must be a $p$ not in $1,2,\dots,n$ such that $p\equiv 3\pmod 4$.

• Yes, thanks for the answer. Stupid question but why exactly does $N=p_1p_2\dots p_k$ and $p_i\equiv 1\pmod 4$ imply $N\equiv 1\pmod 4$? I am probably being really stupid but I don't see it right now – MyNameIs Jul 23 '16 at 15:24
• @MyNameIs $N=p_1 \cdot p_2 \cdot p_3\cdots p_k \equiv 1 \cdot 1 \cdot 1 \cdots 1 = 1 \mod 4$. – wythagoras Jul 23 '16 at 16:18

I think that proof proves there are infinite primes that are $1\bmod 4$ (which is harder in my opinion).

The point if a prime $p$ divides $n!^1+1$ we have $p>n$ and $-1\equiv (n!)^2\bmod p$. Therefore $-1$ is a quadratic residue $\bmod p$, and so $p\equiv 1 \bmod 4$.

So for every positive integer $n$ there is a prime $p$ with $p>n$ and $p\equiv 1\bmod 4$. This proves there are infinite primes $1\bmod 4$

A simple proof there are infinite primes that are $3\bmod 4$:

Suppose there is a finite number of primes that are $3\bmod 4$, let them be $p_1,p_2\dots p_n$

notice that $4p_1p_2\dots p_n - 1$ must have a prime divisor that is $3\bmod 4$.

• By the way, your first statement is wrong. $-1$ is quadratic residue if and only if $p\equiv 1\pmod 4$. – Thomas Andrews Jul 23 '16 at 15:01
• oh yeah, then their proposde proof is wrong? – Jorge Fernández Hidalgo Jul 23 '16 at 15:03
• i think it proves there are infinite primes that are $1\bmod 4$, do you agree? – Jorge Fernández Hidalgo Jul 23 '16 at 15:04
• OPs proposed proof is a correct proof of infinitude of primes $1\pmod 4$. – Wojowu Jul 23 '16 at 15:04
• @CarryonSmiling OP is asking two things, and the first part is a proposed solution to a different question from the question in the title. – Thomas Andrews Jul 23 '16 at 15:06

Qu.1. You need to show, given some $m=(n!)^2+1$, $n>1$, that there is always some prime divisor $p$ of $m$ such that $p\equiv1\pmod{4}$. Once done you have an infinite number of such primes as you have an infinite amount of numbers of the form $m$. Since you have $$(n!)^2\equiv m-1 \equiv -1\pmod{p}\qquad (A)$$ then raising this to the $\frac{(p-1)}{2}$th power gives us $$(n!)^{p-1}\equiv (-1)^ {\frac{(p-1)}{2}}\pmod{p}\qquad (B)$$ Recall Fermat's Little Theorem (FLT): If $\gcd(a,p)=1$ then $a^{p-1}\equiv 1\pmod{p}$. Then by FLT (B) becomes: $$(n!)^{p-1}\equiv 1\pmod{p}\qquad (C)$$ and so $(p-1)/2$ must be even, that is $p-1=4k$ for some $k\ge1$. Note the finite field of $p$ elements, $\mathbb{F}_p$, has an underlying multiplicative cyclic abelian group of nonzero elements (the class $[p]$ acts as the zero in $\mathbb{F}_p$), which means there is a generator $g\in\mathbb{F}_p^\times$ whose powers $\{g,\ g^2, g^3,\dotsc, g^{p-2},\ g^{p-1}=1\}$ generate all of $\mathbb{F}_p^\times$ (there are $\phi(\phi(p))=\phi(p-1)$ of these, where $\phi$ is Euler's Totient Function which measures the numbers in the range $1\le k\le p-1$ for which $\gcd(k,p-1)=1$, with these such $k$ being the generators).

When you had $(n!)^{4}\equiv 1\pmod{p}$ on squaring (A), this meant $n!$ has order $4$ in $\mathbb{F}_p^\times$, with order meaning the first power of $n!$ to give the multiplicative identity in $\mathbb{F}_p^\times$, which by Lagrange's Theorem means $4$ divides the order of the group, which is $|\mathbb{F}_p^\times|=p-1$, and $n!$ generating a cyclic subgroup of order $4$, because every finite subgroup of the multiplicative group of a field is cyclic. Hence $p=4k+1$ for some $k\ge1$ as before. So your proof is fine.

Qu.2. If we consider $n!$, then as long as we take $n\ge4$, we have $n!\equiv 4\equiv 0\pmod{4}$, since $4$ is always contained in the product of $n!$. Now we obtain $n!-1\equiv3\pmod{4}$ on subtracting $1$ in the congruence.

(Note: If all primes are of the form $p=4k+1$ so is their product, e.g. $$p_1\cdot p_2=(4j+1)(4k+1)=4(4kj+j+k)+1$$ whereas the other two cases to consider are: $$p_1\cdot p_2=(4j+1)(4k+3)=4(4kj+3j+4k)+3$$ $$p_1\cdot p_2=(4j+3)(4k+3)=4(4kj+3(j+k)+2)+1$$ so you need an odd number of primes of the form $4k+3$ to give a factorisation $\equiv 3\pmod{4}$.)

Since no prime $p\le n$ can divide $m=n!-1$, we must have any prime divisor of $m$ being $>n$. For a contradiction let us assume all the primes congruent to $3\pmod{4}$ are $<n$. Now consider the prime factorisation of $n!-1$: $$n!-1=\big(\prod_{i=1}^{k}p_{i}^{a_i}\big)-1=\prod_{i=1}^{j}q_{i}^{b_i}\equiv 3\pmod{4},\qquad a_{i},\ b_{i}\ge1$$ where each of the necessarily odd $q_{i}$ primes is congruent to either $1$ or $3$ modulo $4$. It follows at least one of the primes $q_i$ must be congruent to $3$, since otherwise $n!-1$ would be congruent to $1$ modulo $4$. Hence $q_i$ is one of the $p_i$, but all the $q_i$ are strictly greater than any $p_i$ so we have a contradiction. Hence there are infinitely many primes $q\equiv 3\pmod{4}$.

Moreover as a side result there are always an odd number of prime factors of the form $p=4k+3$ in $n!-1$ for $n\ge4$.