# Modular arithmetic - primes of the form $4k-1$

(a)Show that a product of numbers of the form $4k+1$ also have this form.

Easy peasy: Using modular arithmetic: $a_1 a_2 \cdots a_n = 1\cdot 1\cdots1 = 1\ \pmod 4$.

(b)Deduce that if $n=-1 \pmod 4$ and $n>0$ then $n$ must have a prime factor $q=-1 \pmod 4$.

By the fundamental theorem of arithmetic $n$ can be written as a product of primes. I said that every prime is of the form $4k-1$ or $4k+1$ since $4k+2$ and $4k$ cannot possibly be primes (they are divisible by $2$) and $4k+3 = 4(s+1)-1$. But from above a product of number of the form $4k+1$ have the form $4k+1$. So n must have one prime factor of the form $4k-1$.

(c) Show that for $m\geq 4$, $n=m!-1$ has a prime factor $q=-1\pmod 4$ and $q>m$. Deduce that the primes of the form $4k-1$ are infinite.

$n=m!-1$ means $n=-1\pmod 4$ since $4$ is a factor of $m!$ for $m\geq4$. The prime factor part follows from part (b). I had some trouble proving $q>m$. I tried a contradiction argument: Suppose $q\leq m$. Then got $m≥1$ and $m≥4$. Contradiction? Or $m=2$ gives no prime factors. I'm guessing the infinite bit follows from $q>m$?

(d) What happens if we replace 4 by 6 or by 8 in parts a,b,c. I said the same results apply but I am not sure.

• Tiny critique: $4k+2$ can possibly be prime—but only once, and $2$ can't divide a number $n\equiv-1\pmod4$ (why?). – Greg Martin Jan 17 '16 at 22:32
• 2|(4s-1) means 2|1 which is not possible (in Z) – Jack Jan 17 '16 at 22:38

(c) The reason that $q\gt m$ is that if we had $q\le m$, then $q$ would divide $m!$, and therefore $q$ would divide $m!-(m!-1)$.
(d) A very similar argument works for $6$ instead of $4$. Things become more complicated for $8$, since a number of the form $8k-1$ need not have a prime divisor of the form $8k-1$. For instance, $(3)(5)\equiv -1\pmod{8}$.
• For $6$, I would suggest repeating the argument. The basic structure is the same, a product of numbers of the form $6k+1$ is of the form $6k+1$, so any positive integer of the form $6k-1$ has a prime divisor of the form $6k-1$. For $8$, the argument breaks down, and all you need is the example of the answer. There are infinitely many primes of the form $8k-1$, but proving it requires more machinery (quadratic residues). – André Nicolas Jan 17 '16 at 22:13
• Why does $2\le q\le m!$ imply that $q$ divides $m!$? Because then $q$ was one of the numbers that got multiplied together to make $m!$. As to the infinitude, if you show that for any $m$ there is a prime of the right form $\gt m$, then you have shown that there are infinitely many of the right form. – André Nicolas Jan 17 '16 at 22:16