3
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Sorry, but how do you know an odd prime factor of n is congruent to 1 or -1 mod 4? $\endgroup$ – gs2341 Jan 13 '16 at 19:23
  • $\begingroup$ @gs2341 Because the other possible numbers modulo $4$ namely $4k$ and $4k+2$ are always even numbers . $\endgroup$ – user252450 Jan 13 '16 at 19:26
  • $\begingroup$ @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.... $\endgroup$ – N. S. Jan 13 '16 at 19:26
  • $\begingroup$ Of course, thank you! $\endgroup$ – gs2341 Jan 13 '16 at 19:55
  • $\begingroup$ For the same reason, an odd prime is congruent to $\pm 1$ modulo $6$. $\endgroup$ – Bernard Jan 13 '16 at 19:58
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

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

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 .

$\endgroup$

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.