(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.

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

  • $\begingroup$ For part (d) it says conclude. Do I have to repeat the arguments again or is there a better solution? $\endgroup$ – Jack Jan 17 '16 at 22:07
  • $\begingroup$ @Jack: You can repeat the argument for part (b), then you should be able to state (c) in sufficient generality that (c) follows from (b) regardless of whether you use 4 or 6. $\endgroup$ – Snow Jan 17 '16 at 22:08
  • $\begingroup$ Why does q≤m imply q|m! I see the next bit implies q|1 which of course cannot happen since q>1. And for the infinite numbers of primes of the form 4k-1 - Do I say m approaches infinity so q does (q<m)? $\endgroup$ – Jack Jan 17 '16 at 22:11
  • $\begingroup$ 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). $\endgroup$ – André Nicolas Jan 17 '16 at 22:13
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jan 17 '16 at 22:16

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.