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?
On
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 .
On
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$
On
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$.
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$.