# Number TheoryPrime problem

#### Poirot

##### Banned
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 infintely 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.

#### Opalg

##### MHB Oldtimer
Staff member
Re: prime problem

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

#### Poirot

##### Banned
Re: prime problem

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

#### Opalg

##### MHB Oldtimer
Staff member
Re: prime problem

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

#### topsquark

##### Well-known member
MHB Math Helper
Re: prime problem

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

#### Poirot

##### Banned
Re: prime problem

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.