# Congruences and prime numbers

I was first asked to show that a product of numbers of the form $4k+1$ also has this form. I got stuck on the next part: Deduce that if $n \equiv −1 \pmod 4$ and $n > 0$ then $n$ must have a prime factor

$q \equiv −1 \pmod 4$.

Would someone be able to help?

• What is the smallest value $n$ could be? – abiessu Jan 13 '16 at 18:11

Hint:

An odd prime factor is congruent to either $1$ or $-1$ modulo $4$. If all prime factors are congruent to $1$, $n$ is congruent to $1$.

• Sorry, but how do you know an odd prime factor of n is congruent to 1 or -1 mod 4? – gs2341 Jan 13 '16 at 19:23
• @gs2341 Because the other possible numbers modulo $4$ namely $4k$ and $4k+2$ are always even numbers . – user252450 Jan 13 '16 at 19:26
• @gs2341 Any number has a remainder of $0,1,2,3$ when divided by $4$. If the remainder is $2$ or $0$ then the number is even.... – N. S. Jan 13 '16 at 19:26
• Of course, thank you! – gs2341 Jan 13 '16 at 19:55
• For the same reason, an odd prime is congruent to $\pm 1$ modulo $6$. – Bernard Jan 13 '16 at 19:58

Let's say $n \equiv -1 \pmod 4$ and $n = pq$, where $p$ and $q$ are primes.

If $p \equiv q \equiv 1 \pmod 4$, then $pq \equiv 1 \pmod 4$, which I believe you have already proven. And if both $p \equiv q \equiv -1 \pmod 4$, then $pq \equiv 1 \pmod 4$ anyway.

But if $p \equiv 1 \pmod 4$ and $q \equiv -1 \pmod 4$, or the other way around, then $pq \equiv -1 \pmod 4$.

This means that if $n$ is composite and of the form $4k + 1$, it may have a prime factor of the form $4k - 1$, but if $n$ is of the form $4k - 1$, it certainly does have a prime factor of the form $4k - 1$.

Factorize a few small composite numbers of the form $4k - 1$ to convince yourself: $15, 27, 35, 39, 51, 55, 63, 75, 87, 91, 95, 99, \ldots$

All primes are either equal to 2, or equal to $4k + 1$ or $4k - 1$. Products of primes where one prime is 2 are even. Products of primes where all primes are of the form $4k + 1$ are themselves of the form $4k + 1$.

Therefore, if a number $x$ is of the form $4k - 1$, then it isn't a product involving the prime $2m$ and it isn't a product of all primes of the form $4k + 1$. What other possibilities are there? At least one factor must be of the form $4k - 1$.

• Or any odd number of factors is congruent to $-1 \pmod 4$. – Robert Soupe Jan 14 '16 at 4:18

Assume that $n$ has all prime factors of the form $4k+1$. This means $n$ is the product of numbers of the form $4k+1$ .

Then from the first part it follows that $n \equiv 1 \pmod{4}$ which is a contradiction .