Welcome to our community

Be a part of something great, join today!

Number Theory Proof p=1 mod 4 if p|x^2+1

  • Thread starter
  • Admin
  • #1

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
Problem statement

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


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?
 

dwsmith

Well-known member
Feb 1, 2012
1,673
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.
 
  • Thread starter
  • Admin
  • #3

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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? :confused:
 
  • Thread starter
  • Admin
  • #4

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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).