8
$\begingroup$

I'm having difficult proving this.

As a hint the exercise to prove first, that if $a\lneqq \pm 1$ satisfies $a \equiv 3 \pmod4$, then exist $p$ prime, $p \equiv 3 \pmod 4$ such $p\mid4$. But I'm not really getting for what purpose can this be used.

$\endgroup$
7
$\begingroup$

If there are only finitely many primes $\equiv 3 \pmod 4$, take the product of them and denote that product by $a$. Now look at $2a + 1$, and try to deduce a contradiction.

$\endgroup$
  • $\begingroup$ Yes, this really only requires a manipulation of Euclid's proof. $\endgroup$ – Newb Feb 10 '14 at 22:06
  • $\begingroup$ Hey, how would you do that? Just started thys type of problems and can't see it :( @Arthur $\endgroup$ – iggykimi Feb 3 at 18:42
  • 1
    $\begingroup$ @iggykimi How familiar are you with Euclid's proof that there are infinitely many primes? $\endgroup$ – Arthur Feb 3 at 18:44
  • $\begingroup$ I know the one where you take all the primes and add 1, but if that isn't enough for me to understand it is fine @Arthur $\endgroup$ – iggykimi Feb 3 at 18:45
  • 1
    $\begingroup$ @iggykimi That's the one. In this one, we do basically the same thing. We are exploiting the fact that if we multiply together numbers and the result is congruent to $3$ modulo $4$, then at least one of those numbers must be congruent to $3$ modulo $4$. But when we multiply together all our primes to get $a$, we don't know if the result is congruent to $1$ or $3$ (it's odd, so those are the only options). However, $2a+1$ is guaranteed to be congruent to $3$, and it's coprime to all our primes. And one of the prime factors of $2a+1$ must be congruent to $3$. Contradiction. $\endgroup$ – Arthur Feb 3 at 19:02
3
$\begingroup$

Lemma. If $a\equiv 3 \pmod 4$ then there exists a prime $p$ such that $p\mid a$ and $p\equiv 3 \pmod 4$.

Proof. Clearly, all primes dividing $a$ are odd. Suppose all of them would be $\equiv 1 \pmod 4$. Then their product would also be $a\equiv 1\pmod4$, which is a contradiction. $\hspace{3cm}\square$

There exist infinitely many primes $p$ such that $p\equiv 3\pmod 4$.

Suppose that $p_1,\dots,p_n$ would be all such primes. Take $a=4p_1\cdots p_n+3$. (Or you can take $a=4p_1\cdots p_n-1$.) Show that $p_i\nmid a$ for $i=1,\dots,n$. Then use the above lemma to get a contradiction.

$\endgroup$
2
$\begingroup$

Use Euclid's proof showing that there are infinitely many primes, i.e., find an Euclidean polynomial you can use for your arithmetic progression $l \mod k$. Since $l^2\equiv 1 \mod k$ such an Euclidean polynomial exists - see http://www.mast.queensu.ca/~murty/murty-thain2.pdf how to do it (in particular, on page one, the case $4n+3$ is given, see [5]). For $8n+1$ see Infinitely many primes of the form $8n+1$.

$\endgroup$
1
$\begingroup$

Show that there are infinitely many primes that are congruent to 3 mod 4. (Hint: Use that $4\mid(p_1p_2\cdots p_r + 3)$.

Solution: Suppose there are finitely many primes p congruent to 3 mod 4 and denote them by (noting that 3 is one of them) $3, p_1, p_2, p_3,\dotsc, p_r$.

Now consider $A = 4p_1p_2\cdots p_r+5$. If $A$ is prime, then we are done since it is clearly congruent to 3 mod 4 and it is not one of the $p_i$ (as it is greater than all of them). If not, then $A$ has a prime factorization:

$$A = q_1q_2\cdots q_s.$$

Now observe that any prime greater than 3 has to be congruent to 1 or 3 mod 4. This is because, if it were congruent to 0, 2 or 3 mod 4, it would be even, and if it were congruent to 3 mod 4, then it would have to be 3 (only numbers congruent to 3 mod 6 are multiples of 3). Thus each of the $q_i$ has to be congruent to 1 or 3 modulo 4.

However, not all the $q_i$ can be congruent to 1 mod 4. If they were, then their product, which is $A$, could also have to be congruent to 1 mod 4, and this is not possible by construction (note that it would be possible if we had included 3 as one of the factors in the product $4p_1p_2\cdots p_r$).

Thus there exists at least one $q_i$ which is congruent to 3 mod 4. However, this cannot be one of the primes $3, p_1, p_2, p_3,\dotsc,p_r$. If it were, then $q_i$ would divide $A$ (since it is in the prime facorization of $A$) and it would divide $4p_1p_2\cdots p_r$ (since it is one of the primes in that product), and it thus has to divide their difference, which is 3. Thus $q_i$ has to be 3, but that’s a contradiction since 3 does not divide $4p_1p_2\cdots p_r$.

$\endgroup$
  • 1
    $\begingroup$ How is $A = 4p_1p_2\cdots p_r+5$ congruent to $3$ mod $4$? Isn't it congruent to $1$ mod $4$? $\endgroup$ – Al Jebr Mar 2 '18 at 0:39

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.