Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$n = 4k + 3 $

We start by letting $a \not\equiv 0\pmod n$ $\Rightarrow$ $a \equiv k\pmod n$ .

$\Rightarrow$ $a^{4k+2} \equiv 1\pmod n$

Now, I know that the contradiction will arrive from the fact that if we can show $a^2 \equiv 1 \pmod n $ then we can say $b^2 \equiv -1 \pmod n $ then it is not possible since solution exists only for $n=4k_2+1 $ so $a \equiv b\equiv 0 \pmod n $

So from the fact that $a^{2^{2k+1}} \equiv 1 \pmod n$ I have to conclude something.

share|improve this question

5 Answers 5

up vote 3 down vote accepted

Hint: If $p \equiv 3 \pmod{4}$, then $x$ is a quadratic residue $\bmod{p}$ if and only if $-x$ is a quadratic nonresidue $\bmod{p}$.


Edit, to be more direct:

Lemma: Suppose that $p$ is an odd prime, and assume that $x$ is a nonzero quadratic residue $\bmod{p}$. Then, $-x$ is a quadratic residue $\bmod{p}$ if and only if $p \equiv 1 \pmod{4}$.

Proof:

First suppose that $p \equiv 1 \pmod{4}$. By assumption, as $x$ is a nonzero quadratic residue, there exists an integer $a \neq 0$ such that $a^2 = x$. Since $-1$ is also a quadratic residue, there also exists an integer $b$ such that $b^2 = -1$. Thus, $$ -x = -1 x = b^2 a^2 = (ba)^2, $$ and hence $-x$ is a quadratic residue.

On the other hand, suppose that $p \equiv 3 \pmod{4}$ and $x = a^2$ is a quadratic residue. Since $x \neq 0$, it follows that $-x \neq 0$ as well. Then, suppose for a contradiction that $-x$ is also a nonzero quadratic residue, and hence $-x = c^2$ for some $c$. If this were the case, it would follow that $$ -1 = -x/x = c^2/a^2 = (c/a)^2 $$ which would imply that $-1$ is a square $\bmod{p}$. This gives a contradiction, and we conclude that if $p \equiv 3\pmod{4}$ and $x$ is a nonzero quadratic residue, then $-x$ must be a quadratic nonresidue.

share|improve this answer
    
This makes sense but we're not supposed to use a quadratic residue result yet. Maybe I should read the proof of this statement and try deriving it. –  Rohan Feb 2 '12 at 18:16
    
Are you aware of the result that if $p \equiv 3\pmod{4}$, then $-1$ is not a square $\bmod{p}$? –  JavaMan Feb 2 '12 at 18:18
    
Yes. the equation has a solution iff $p=4k+1$ –  Rohan Feb 2 '12 at 18:24
    
If $x$ is a square and $-x$ is square, then (assuming $x \neq 0$), it must be that $-x/x = -1$ is also a square (this follows since $m^2/n^2 = (m/n)^2$). However, $-1$ cannot be a square since $p \equiv 4k + 3$. Thus, $-x$ also cannot be a square. –  JavaMan Feb 2 '12 at 18:27
    
I get this but $a^2 \equiv k \pmod n $ and not necessarily $a^2 \equiv 1 \pmod n $ . –  Rohan Feb 2 '12 at 19:20

Assume that $a$ and $b$ are coprime. If $a$ and $b$ are odd, replace $a$ and $ b$ by $(a-b)/2$ and $(a+b)/2$. Then $a^2 + b^2 = pm$, and by reducing $a$ and $b$ modulo $p$ you can make sure that $m < p$. Since $p = 4n+3$ and $a^2 + b^2 = 4k+1$, we must have $m = 4j+3$. But then $m$ is divisible by a prime number $q = 4r+3$ strictly smaller than $p$. Repeat until you find that $3$ is a sum of two squares.

share|improve this answer

You are on the right track, the problem is that you don't know what $a^2$ is to relate it to $b^2$.

Hint Can you relate somehow $a^{4k+2} \equiv 1\pmod n$ to $b$?

Edit: Since you figured it, here is the complete solution.

First note that if we prove $a \equiv 0\pmod p$ it follows imediately that $b$ is also $0 \pmod p$.

Thus it is enough to prove that $a \equiv 0 \pmod p$. Assume by contradiction that is not true. Then, since $p$ is prime, by Fermat Little Theorem,

$$1=a^{p-1}=a^{4k+2}=(a^2)^{2k+1}=(-b^2)^{2k+1} =(-1)^{2k+1}b^{4k+2}=-b^{4k+2} (*)$$

But $b^2= -a^2$ is invertible, thus $b \neq 0 \pmod p$. Hence

$$b^{4k+2}=b^{p-1} = 1 \pmod p$$

Thus $(*)$ implies $1=-1 \pmod p$, contradiction.

share|improve this answer
    
${{(-b^2)}^{2k+1}} \equiv 1 \pmod n \Rightarrow {b}^{2^{2k+1}} \equiv {-1} \pmod n $ which implies $ 1 \equiv {-1} \pmod n $ hence contradiction . It sounds fine to me. Is it good? –  Rohan Feb 2 '12 at 18:21
    
Yep, that's it. I added the details. –  N. S. Feb 3 '12 at 2:23

p is prime / p=4k+3 if: p=xˆ2 +2*yˆ2 if: p = 3 (mod 8) and p = xˆ2 -2*yˆ2 if: p = 7 (mod 8) / p=xˆ2-c*yˆ2 / c=-2 if p=3 mod 8 and c=2 if p=7 mod 8

and exist a in (1,p-1) / (+-a)ˆ2=c (mod p) and: if p=3 mod 8 then not exist x´ and y´ / p (not= ) x´ˆ2+2*yˆ2 if p=7 mod 8 then not exist b in (1,p-1) / (+-b)ˆ2 not congruent with c mod p

examples: 1) p=11= [3]ˆ2 +2*[1]ˆ2 c=-2 and mcd[3,1]=+-1 exist a/aˆ2=-2 mod p / a=3 (and p-3) 2) p=27= [3]ˆ2 + 2*[3]ˆ2=[5]ˆ2+2*[1] then p not prime because exist x´... 3) p=23 c=2 only exist a=23 / (+-a)ˆ2=2 mod p if exist b not a / (+-b)ˆ2 mod p then p not prime if you want send me a email: miguelangelreybonet@yahoo.es

share|improve this answer
    
Can you please edit your answer using LaTeX? –  Ludolila Jan 22 at 10:43
1  
@miguel rey, Welcome to SE. Please write your posts using LaTeX, the answer is illegible. –  Sepideh Bakhoda Jan 22 at 11:27
    
Also, I strongly advise you not to make your email adress public. Anyone can read this, so this makes your email easily accessible for spam bots. –  barto Jan 22 at 21:20

This is solution from Prasolov V.V. Zadachi po algebre, arifmetike i analizu (В. В. Прасолов. Задачи по алгебре, арифметике и анализу.) This book (in Russian) is freely available at http://www.mccme.ru/free-books/

The problem appears there as Problem 31.2.

We want to show that if $p=4k+3$ is a prime number and $p\mid a^2+b^2$, then $p\mid a$ and $p\mid b$.

My translation of the solution given there:

Suppose that one of the numbers $a$, $b$ is not divisible by $p$. Then the other one is not divisible by $p$, either. Thus from Fermat's little theorem we get $a^{p-1} \equiv 1 \pmod p$ and $b^{p-1} \equiv 1 \pmod p$. This implies $a^{p-1}+b^{p-1} \equiv 2 \pmod p$.

On the other hand, the number $a^{p-1}+b^{p-1}=a^{4k+2}+b^{4k+2}=(a^2)^{2k+1}+(b^2)^{2k+1}$ is divisible by $a^2+b^2$, and thus it is divisible by $p$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.