Question

show that \[\large p | (x^2+1) \text{ has a solution } \iff p = 4k+1\]

\(p\) is an odd prime

Answer 1

Well, let's see. we know that p is a prime number, that means it is odd (not even).
But as you say it is defined as \(x^2 + 1\). That means \(x\) has to be an even integer, because \(x^2\) has to be an even integer.
Only that way adding 1 to it would end up with an odd integer which is a requirement for a prime number.
That means \(\frac{1}{2}x\) is an integer as well. So now we can say \(k = \bigg( \frac{1}{2}x\bigg)^2 = \frac{1}{4}x^2\)
So now for any such nubmer we have a 'k' which satisfies
$$ 4k + 1 = 4 \cdot \bigg( \frac{1}{4}x^2 \bigg) + 1 = x^2 + 1= p$$

Answer 2

Well thanks. I didn't show the other way around, but it's very similar =)

Answer 3

Wow. I don't even understand the question...

Answer 4

hmm is it Lagrange theorem ?

Answer 5

Yes... that works i guess

Answer 6

\(x^2+1\equiv 0 \mod p\\ gcd(1,p)=1 ~~and~ gcd(4,p)=1\\ ~thus ~ \\x^2+1\equiv 4(x^2+1) \equiv 0 \mod p \\ 4x^2\equiv -4 \mod p \\let~ y=2x \\ (2x)^2\equiv -4 \mod p \\ y^2\equiv -4 \mod p \\
\text{let y_0 be a solution } \\ y_0\equiv -4 \mod p\\
y_0+4=kp\\
y_0=kp-4 \\ 2x\equiv y_0-p \mod p\)
hmm dont feel this ends it good, i'll make lunch brb

Answer 7

and i have something with @pitamar solution
x need not to be odd
hmm
see 3|6 and 6 is even

Answer 8

I see you're using quadratic residues... that works perfectly, we need to tweak it a bit more ...

Here is another proof with a big flaw :

By Fermat's little theorem we have
\(\large x^{p-1}\equiv 1\pmod{p}\tag{1}\)

\(\large x^2\equiv -1\pmod{p}\)
squaring both sides
\(\large x^4\equiv 1\pmod{p}\tag{2}\)



from (1) and (2)
\[4|(p-1) \implies p = 4k+1\]

Answer 9

eh that was so quick i dint even got the chance to think xD

Answer 10

i was trying to use lagrange thingy

Answer 11

lagrange theorem gives you solution in one line

Answer 12

haha yeah it only says blah blah have solution iff p=4k+1 =)
so thought of thinking its proof

Answer 13

discrete logarithm is much better :

\[x^2\equiv -1 \pmod{p}\]
take discrete logarithm both sides :
\[2 \log x \equiv \log (-1) \pmod{p-1}\]
\[2 \log x \equiv \frac{p-1}{2} \pmod{p-1}\]

for this congruence to admit a solution, we need \(\gcd(2, p-1) | \frac{p-1}{2}\)

Answer 14

but gcd(2, p-1) is 2 itself so we have
\(2 | \dfrac{p-1}{2} \implies p = 4k+1\)

Answer 15

wanna see the proof using lagragne thm ?

Answer 16

sure
i forgot these stuff =)

Answer 17

I keep seeing these but I don't ever seem to understand them even after reading and sort of seeing an explanation for some reason, what's wrong with me lol

Answer 18

Another proof w/o appealing directly to lagrange thm :


\(\large (\Leftarrow )\)
suppose \(p = 4k+1\) and consider below congruence
\(x^4\equiv 1 \pmod{p}\)

factoring gives
\((x^2+1)(x^2-1)\equiv 0 \pmod{p}\)

because \(p\) is a prime it follows that
\(x^2+1 \equiv 0 \pmod p\) or \(x^2-1\equiv 0 \pmod{p}\)

letting \(x\) be primitive root, we see that \(x^2-1\not \equiv 0 \pmod{p}\)
that yields \(x^2+1 \equiv 0 \pmod p\) \(\blacksquare\)

Answer 19

Maybe I'll let you work the proof using lagrange thm :)

Answer 20

haha ok

Answer 21

Lagrange
`if p is prime and f(x) polynomial with leading coefficient a such that` `gcd(a,p)=1 (great power is n)`
`and` \( f(x)\equiv 0 \mod p\) `has at most n incongruent solution modulo p`
so
\(x^2+1\equiv p\) has 2 solution
hehehe so far i tried previous stuff and got stuck

Answer 22

Oh that can be pretty lengthy.. we can use below version of lagrange thm :
\(x^k\equiv a \pmod p\) has a solution \(\iff\) \(a^{(p-1)/d}\equiv 1\pmod{p}\) where \(d = \gcd(k,p-1)\)

Answer 23

got it !!

Answer 24

x^2=-1 mod p

-1^(p-1)/2=1 mod p

p-1 = 4k ( we need -1^b such that b is even)

p=4k+1

x'D

Answer 25

like
p-1/2= 2k to make -1^something=1
p-1=4k

Answer 26

thats it! p = 4k+3 is not possible because then (p-1)/2 becomes odd

Answer 27

thats really nice question

Answer 28

@Kainui I think all these theorems are based around discrete logarithm

Answer 29

we might be able to prove all the stated thms in this thread using just the definition of discrete logarithm

http://en.wikipedia.org/wiki/Discrete_logarithm

Answer 30

haha abstract algebra =)

Answer 31

i thought that at first i couldnt memorize what it was exactly special with the pre question

Answer 32

see
a^k have all modulo classes of p :| and thats it
QED!!