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?

  • $\begingroup$ 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$. $\endgroup$ – darij grinberg Jul 23 '16 at 14:55
  • $\begingroup$ Sorry I meant $n!$ has multiplicative order $4$. I edited it. $\endgroup$ – 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$.

  • $\begingroup$ 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 $\endgroup$ – MyNameIs Jul 23 '16 at 15:24
  • $\begingroup$ @MyNameIs $N=p_1 \cdot p_2 \cdot p_3\cdots p_k \equiv 1 \cdot 1 \cdot 1 \cdots 1 = 1 \mod 4$. $\endgroup$ – 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$.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.