Proof: p=1 mod 4 if p|x^2+1 Problem statement

[I like Serena]

Problem statement

Let n be a whole number of the form $$n=x^2+1$$ with $$x \in Z$$, and p an odd prime that divides n.
Proof: $$p \equiv 1 \pmod 4$$.Attempt at a solution

The only relevant case is if p=3 (mod 4).

If I try to calculate mod 3, or mod 4, or mod p, I'm not getting anywhere.

Help?

 

[Dustinsfl]

Attempt at a solution

The only relevant case is if p=3 (mod 4).

If I try to calculate mod 3, or mod 4, or mod p, I'm not getting anywhere.

Help?

What? 3 isn't congruent to 1 mod 4. p = 5 would work since 5 is congruent to 1 mod 4 and 5|(x^2+1) when x = pm 2.

Now have can you show that if n is an integer such that p|n then p is congruent to 1 mod 4.

I don't know at the moment but I will think about it more.

 

[I like Serena]

What? 3 isn't congruent to 1 mod 4. p = 5 would work since 5 is congruent to 1 mod 4 and 5|(x^2+1) when x = pm 2.

Now have can you show that if n is an integer such that p|n then p is congruent to 1 mod 4.

I don't know at the moment but I will think about it more.

Thanks for replying.

Since p is odd, it is either congruent to 1 or 3 mod 4.
If it is congruent to 1, we have what we need to proof.
So we need to proof that if p=3 mod 4 it would lead to a contradiction.

If we check for instance p=3, we can tell that x^2+1=1,2 mod 3, which is a contradiction (since p=0 mod 3).
With p=7, we can check all possibilities mod 7, which indeed also leads to a contradiction.
Same with p=11.

But how can we generalize this?

 

[I like Serena]

I received a hint for this problem (a first year algebra problem btw).

It's:
Hint: determine the order of x in Z/pZ*.

I've got it! I've got it! :D

 

[caffeinemachine]

I received a hint for this problem (a first year algebra problem btw).

It's:
Hint: determine the order of x in Z/pZ*.

I've got it! I've got it! :D

here's a proof which is essentially the same as you have pointed out but little more straight forward:

$x^2 +1 \equiv 0 \mod p$
$\Rightarrow x^2 \equiv -1 \mod p$ ----> we get order of $x$ mod $p$ is not 2.
$\Rightarrow x^4 \equiv 1 \mod p$. ----> one can now easily conclude that the order of $x$ mod $p$ is $4$.

Thus $4|(p-1)$. why? (hint: Fermat's little theorem).