MHB Are there infinitely many primes that satisfy $p=3$ mod4 and divide $x^2+2$?

  • Thread starter Thread starter Poirot1
  • Start date Start date
  • Tags Tags
    Prime
AI Thread Summary
The discussion centers on proving the existence of infinitely many primes \( p \) such that \( p \equiv 3 \mod 4 \) and \( p \) divides \( x^2 + 2 \) for odd natural numbers \( x \). It is established that \( x^2 + 2 \equiv 3 \mod 4 \) when \( x \) is odd, indicating that there must be a prime divisor \( p \equiv 3 \mod 4 \). The participants explore the implications of prime divisors being either \( 1 \) or \( 3 \mod 4 \), concluding that they cannot all be \( 1 \mod 4 \) since this would contradict the earlier result. Finally, a method is suggested to generate an infinite list of such primes by constructing \( x \) from the product of known primes congruent to \( 3 \mod 4 \). The discussion concludes with the affirmation that the existence of such primes is established.
Poirot1
Messages
243
Reaction score
0
1)show that for an odd natural number x, $x^2+2=3$ mod4.

2)Deduce that there exist a prime p such that $p=3$ mod4 and p|$x^2+2$

3)Use this to prove there are infinitely many primes p such that $p=3$ mod 4

1) is easy just writing x=2m+1

2) and 3) I don't know what to do.
 
Mathematics news on Phys.org
Re: prime problem

Poirot said:
1)show that for an odd natural number x, $x^2+2=3$ mod4.

2)Deduce that there exist a prime p such that $p=3$ mod4 and p|$x^2+2$

3)Use this to prove there are infinitely many primes p such that $p=3$ mod 4

1) is easy just writing x=2m+1

2) and 3) I don't know what to do.
For 2), think about the prime divisors of $x^2+2$. They can't include $2$ (because $x^2+2$ is odd), so they must all be congruent to $1$ or $3\pmod4$. Why can't they all be congruent to $1\pmod4$?

For 3), build up a list $p_1,\ p_2,\ p_3,\ldots$ of primes congruent to $3\pmod4$. If you already have $p_1,\ldots,p_n$, let $x$ be the product $p_1p_2\cdots p_n$ and use 2) to find a new prime $p_{n+1}$ to add to the list.
 
Re: prime problem

Opalg said:
For 2), think about the prime divisors of $x^2+2$. They can't include $2$ (because $x^2+2$ is odd), so they must all be congruent to $1$ or $3\pmod4$. Why can't they all be congruent to $1\pmod4$?

For 3), build up a list $p_1,\ p_2,\ p_3,\ldots$ of primes congruent to $3\pmod4$. If you already have $p_1,\ldots,p_n$, let $x$ be the product $p_1p_2\cdots p_n$ and use 2) to find a new prime $p_{n+1}$ to add to the list.

If they are all congruent to 1 mod 4, then x^2+2 is congruent to 1 mod 4. Which implies
4|x^2-1. This is not impossible e.g x=5
 
Re: prime problem

Poirot said:
If they are all congruent to 1 mod 4, then x^2+2 is congruent to 1 mod 4.
That is correct. But you have shown in 1) that x^2+2 is congruent to 3 mod 4. So the assumption that they are all congruent to 1 mod 4 must be false ... .
 
Re: prime problem

Opalg said:
For 2), think about the prime divisors of $x^2+2$. They can't include $2$ (because $x^2+2$ is odd), so they must all be congruent to $1$ or $3\pmod4$. Why can't they all be congruent to $1\pmod4$?
I'm going to chime in real quick. Don't we still have to prove that such a (p,x) exists? Or do we merely note that p = 3, x = 1 suits the bill, therefore existence?

-Dan
 
Re: prime problem

topsquark said:
I'm going to chime in real quick. Don't we still have to prove that such a (p,x) exists? Or do we merely note that p = 3, x = 1 suits the bill, therefore existence?

-Dan

Since x^2+1 >1, it has a prime divisor, and opalg's analysis follows.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top