4k+1 prime

[nayel]

Let $p$ be a prime of the form $4k+1$. Prove that $x^2\equiv -1\pmod{p^n}$ has a solution for each positive integer $n$.

[sourav das]

Solution:

We'll use two theorems:
(1)If $(a,p)=1$ then $ax\equiv b(mod$ $p)$ has a unique solution.

(2) Dirichlet's theorem: For $p$ be odd prime $a^{\frac {p-1}{2}}\equiv 1(mod$ $p)$ is solvable if $x^2 \equiv a(mod$ $p)$ has a solution. Otherwise $a^{\frac {p-1}{2}}\equiv -1(mod$ $p)$ has a solution

For $n=1$, By Fermat, $x^{4k}\equiv 1 (mod$ $p)$ [p=4k+1] for all $x\in A=\{1,2,...p-1\}$ .So $(x^{2k}+1)(x^{2k}-1)\equiv 0 (mod$ $p)$. If, for all $x \in A$ $x^{2k}-1\equiv 0 (mod$ $p)$ then $x^2\equiv a (mod$ $p)$ is solvable for all $a \in A$ by (1). But it is not possible as every $x^2\equiv a (mod$ $p)$ has at least 2 solutions (If solvable). That means we'll get at least $2p-2$(Note: p>3) unique solutions in total for all systems $x^2 \equiv a (mod$ $p)$ for all $a \in A$. Contradiction by Pigeon hole principle. So, at least for one $a$ satisfies $a^{2k}+1 \equiv 0 (mod$ $p)$ By $(2)$ . Case $n=1$ is done.

By induction let $x^2+1= K.p^n$ has a solution $r$ [Clearly $(r,p)=1$] . By (1), $2rx \equiv -K(mod$ $p)$ has a solution as $(2r,p)=1$ consider $x=m$ . So $(r+m.p^n)^2+1=r^2+1 +2m.r.p^n+p^{2n}= K.p^n +2mr.p^n+p^{2n}=(K+2mr) p^n+p^{2n}$ which is divisible by $p^{n+1}$ as $p|K+2mr$ . So $(r+m.p^n)^2 \equiv -1 (mod$ $p^{n+1})$ .

I'm very disappointed with my proof. I used 2 THEORIES. Please some one post a solution comparatively less use of theory and with a trick of nice algebraic substitution if has any...

[afif mansib ch]

i'm confused.i tried it with very simple theorems.is my one correct?
\[p=4k+1\equiv 1(mod4\] so\[p^n\equiv 1(mod4)\Rightarrow p^n-1\equiv 0(mod4)\]
now from fermat,\[x^{p^n-1}\equiv 1(modp^n)\]
\[(x^{2})^{(p^n-1)/2}\equiv (-1)^{(p^n-1)/2}\equiv 1(modp^n)\]
so it has sol for positive integers n.

[sourav das]

You have shown that $x^2 \equiv 1 (mod$ $p)$ has solution. But we need to find $x^2 \equiv -1 (mod$ $p^n)$ has a solution

[*Mahi*]

now from fermat,\[x^{p^n-1}\equiv 1(modp^n)\]

And also, Fermat is true for primes, not prime powers. This might be \[x^{p^n-p^{n-1}} \equiv 1 (mod p^n)\] from Euler.

[Phlembac Adib Hasan]

Solution:
]We'll use two theorems:
(1)If $(a,p)=1$ then $ax\equiv b(mod$ $p)$ has a unique solution.

(2) Dirichlet's theorem: For $p$ be odd prime $a^{\frac {p-1}{2}}\equiv 1(mod$ $p)$ is solvable if $x^2 \equiv a(mod$ $p)$ has a solution. Otherwise $a^{\frac {p-1}{2}}\equiv -1(mod$ $p)$ has a solution

For $n=1$, By Fermat, $x^{4k}\equiv 1 (mod$ $p)$ [p=4k+1] for all $x\in A=\{1,2,...p-1\}$ .So $(x^{2k}+1)(x^{2k}-1)\equiv 0 (mod$ $p)$. If, for all $x \in A$ $x^{2k}-1\equiv 0 (mod$ $p)$ then $x^2\equiv a (mod$ $p)$ is solvable for all $a \in A$ by (1). But it is not possible as every $x^2\equiv a (mod$ $p)$ has at least 2 solutions (If solvable). That means we'll get at least $2p-2$(Note: p>3) unique solutions in total for all systems $x^2 \equiv a (mod$ $p)$ for all $a \in A$. Contradiction by Pigeon hole principle. So, at least for one $a$ satisfies $a^{2k}+1 \equiv 0 (mod$ $p)$ By $(2)$ . Case $n=1$ is done.

Sourav Vaia, Euler proved the modular equation $x^2\equiv-1(mod p)$ has solution iff $p$ is a $4k+1$ type prime.(It directly follows as$(-1)^{\frac {p-1}{2}}\equiv (-1)^{2k}\equiv 1 (mod p)$).So case 1 is proved. My second part is a inductive process like you did.It's easy to understand,i think.

[sourav das]

Actually i like to avoid using direct theorems in number theory (Special case Euler and Fermat). So for solving this problem i had to read and understand the theory first and then apply it. So, i really want to see a proof without (or less) theory used solution....

[Phlembac Adib Hasan]

I have generalized Dirichlet's theorem.(And thanks to Nayel Vaia for giving this problem because I found it while trying to solve this)
Statement :Let $p$ is an odd prime.$a$ is a co-prime of it and $n$ is any positive integer.\[x^2\equiv a \; (mod\; p^n)\; \; has\; \: solution \; \; \Leftrightarrow\; \; a^{\frac {(p-1)p^{n-1}}{2}}\equiv 1\; (mod\; p^n)\]\[x^2\equiv a \; (mod\; p^n)\; \; has\; \: no \; \: solution \; \; \Leftrightarrow\; \; a^{\frac {(p-1)p^{n-1}}{2}}\equiv -1\; (mod\; p^n)\]
I'll give its proof after national.
Nayel Vaia's problem directly follows from my generalization.(putting $a=-1,p=4k+1$)

[*Mahi*]

I have generalized Dirichlet's theorem.(And thanks to Nayel Vaia for giving this problem because I found it while trying to solve this)
Statement :Let $p$ is an odd prime.$a$ is a co-prime of it and $n$ is any positive integer.\[x^2\equiv a \; (mod\; p^n)\; \; has\; \: solution \; \; \Leftrightarrow\; \; a^{\frac {(p-1)p^{n-1}}{2}}\equiv 1\; (mod\; p^n)\]\[x^2\equiv a \; (mod\; p^n)\; \; has\; \: no \; \: solution \; \; \Leftrightarrow\; \; a^{\frac {(p-1)p^{n-1}}{2}}\equiv -1\; (mod\; p^n)\]
I'll give its proof after national.
Nayel Vaia's problem directly follows from my generalization.(putting $a=-1,p=4k+1$)

The proof can be done in quite a similar way to the proof of Euler's criterion...

[Phlembac Adib Hasan]

I have generalized Dirichlet's theorem.(And thanks to Nayel Vaia for giving this problem because I found it while trying to solve this)
Statement :Let $p$ is an odd prime.$a$ is a co-prime of it and $n$ is any positive integer.\[x^2\equiv a \; (mod\; p^n)\; \; has\; \: solution \; \; \Leftrightarrow\; \; a^{\frac {(p-1)p^{n-1}}{2}}\equiv 1\; (mod\; p^n)\]\[x^2\equiv a \; (mod\; p^n)\; \; has\; \: no \; \: solution \; \; \Leftrightarrow\; \; a^{\frac {(p-1)p^{n-1}}{2}}\equiv -1\; (mod\; p^n)\]
I'll give its proof after national.
Nayel Vaia's problem directly follows from my generalization.(putting $a=-1,p=4k+1$)

The proof can be done in quite a similar way to the proof of Euler's criterion...

You've got the trick .Nice.There is another way.(for those who's not got it)Modify Sourav Vaia's inductive proof a little bit to prove this.(Notice that the base case is true from Dirichlet)