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

  • Thread starter Thread starter I like Serena
  • Start date Start date
  • Tags Tags
    Proof
AI Thread Summary
The discussion revolves around proving that if an odd prime p divides n = x^2 + 1, then p must be congruent to 1 modulo 4. Initial attempts focused on the case where p = 3 modulo 4, but this led to contradictions when checking values like p = 3, 7, and 11. The key insight is that if p divides n, then x^2 ≡ -1 mod p implies that the order of x modulo p cannot be 2, leading to the conclusion that the order must be 4. Consequently, this establishes that 4 divides (p - 1), confirming that p ≡ 1 mod 4. The proof hinges on applying Fermat's little theorem to solidify the argument.
I like Serena
Science Advisor
Homework Helper
MHB
Messages
16,335
Reaction score
258
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?
 
Mathematics news on Phys.org
ILikeSerena said:
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.
 
dwsmith said:
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:
 
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
 
ILikeSerena said:
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).
 
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
Back
Top