1. ## Some congruence questions

1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)

2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

Thank you very much in advance!

2. Originally Posted by machack

1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)

2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

Thank you very much in advance!
1.)

$\displaystyle \left(\frac{-a^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)^2 = \left(\frac{-1}{p}\right) = \begin{cases} 1, & \mbox{if } p \equiv 1\mod{4} \\ -1, & \mbox{if } p \equiv 3\mod{4} \end{cases}$

Hence $\displaystyle x^2\equiv -a^2\mod{p}$ is solvable $\displaystyle \iff p \equiv 1\mod{4}$.

2.)

$\displaystyle p\mid a^2+b^2 \implies a^2+b^2\equiv0\mod{p}\implies b^2\equiv-a^2\mod{p} \implies p\equiv 1 \mod{4}$ since $\displaystyle x^2\equiv-a^2\mod{p}$ is solvable.

Here's some work for you: I never explicitly stated that $\displaystyle (a,b)=1$. Let's see if you can figure out where that fact is needed above.

3. Originally Posted by chiph588@
1.)

$\displaystyle \left(\frac{-a^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)^2 = \left(\frac{-1}{p}\right) = \begin{cases} 1, & \mbox{if } p \equiv 1\mod{4} \\ -1, & \mbox{if } p \equiv 3\mod{4} \end{cases}$

Hence $\displaystyle x^2\equiv -a^2\mod{p}$ is solvable $\displaystyle \iff p \equiv 1\mod{4}$.

2.)

$\displaystyle p\mid a^2+b^2 \implies a^2+b^2\equiv0\mod{p}\implies b^2\equiv-a^2\mod{p} \implies p\equiv 1 \mod{4}$ since $\displaystyle x^2\equiv-a^2\mod{p}$ is solvable.

Here's some work for you: I never explicitly stated that $\displaystyle (a,b)=1$. Let's see if you can figure out where that fact is needed above.
For number 2, is it just that we have to show neither of a or b are 0 mod p, after which we can just apply question 1?

Since p|a^2+b^b, either p|a and p|b or p divides neither. The former would contradict (a,b)=1. Right?

Thanks

Edit: also, is there a way to prove question 1 without using the legendre symbol?

4. Originally Posted by machack
For number 2, is it just that we have to show neither of a or b are 0 mod p, after which we can just apply question 1?

Since p|a^2+b^b, either p|a and p|b or p divides neither. The former would contradict (a,b)=1. Right?

Thanks

Edit: also, is there a way to prove question 1 without using the legendre symbol?

Here's a better way to think about #2: Let's work in $\displaystyle \mathbb{Z}[i]$.

$\displaystyle a^2+b^2=(a+ib)(a-ib)$, so $\displaystyle p\mid a^2+b^2\implies p\mid a+ib$ or $\displaystyle p\mid a-ib$. Because $\displaystyle (a,b)=1\implies a+ib \neq p\cdot d$ where $\displaystyle d\in\mathbb{Z}[i]$.
One can deduce from this that $\displaystyle p=(c+id)(c-id) \implies p\equiv 1\mod{4}$

5. Originally Posted by chiph588@

Here's a better way to think about #2: Let's work in $\displaystyle \mathbb{Z}[i]$.

$\displaystyle a^2+b^2=(a+ib)(a-ib)$, so $\displaystyle p\mid a^2+b^2\implies p\mid a+ib$ or $\displaystyle p\mid a-ib$. Because $\displaystyle (a,b)=1\implies a+ib \neq p\cdot d$ where $\displaystyle d\in\mathbb{Z}[i]$.
One can deduce from this that $\displaystyle p=(c+id)(c-id) \implies p\equiv 1\mod{4}$
Does my suggestion work though?
1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)
2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

So to prove problem 2 (that given a^b=-b^2 (mod p) for (a,b)=1, prove p = 1(mod 4)), we can use the "only if" part of problem 1 as long as we can prove that b is not congruent to 0 mod p. And I believe this can be done by saying p|a^2+b^2 -> its impossible for p to divide only one of a or b, and if p could divide both then the GCD of a and b would be at least p (contradicting the given). Thus neither a nor b are congruent to 0 mod p and we can apply "For p an odd prime and a any integer which is not congruent to 0 mod p, the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)".
Does this work?

Also, these are problems for an elementary number theory course and I'm afraid I haven't gotten far enough to understand your new explanation.

6. Originally Posted by machack
Does my suggestion work though?
1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)
2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

So to prove problem 2 (that given a^b=-b^2 (mod p) for (a,b)=1, prove p = 1(mod 4)), we can use the "only if" part of problem 1 as long as we can prove that b is not congruent to 0 mod p. And I believe this can be done by saying p|a^2+b^2 -> its impossible for p to divide only one of a or b, and if p could divide both then the GCD of a and b would be at least p (contradicting the given). Thus neither a nor b are congruent to 0 mod p and we can apply "For p an odd prime and a any integer which is not congruent to 0 mod p, the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)".
Does this work?

Also, these are problems for an elementary number theory course and I'm afraid I haven't gotten far enough to understand your new explanation.
Your arguement is almot correct and the same thing I was hinting at earlier.
We can say WLOG p does not divide b. (For all we know p could divide b and not a.)

It turns out p doesn't divide a or b. Can you see why?

7. Originally Posted by chiph588@
Your arguement is almot correct and the same thing I was hinting at earlier.
We can say WLOG p does not divide b. (For all we know p could divide b and not a.)

It turns out p doesn't divide a or b. Can you see why?
Well we know p can't divide b and not a because if for 3 integers x,y, and z, if x|y+z and x|y, then x|z. In this case, p|a^2 + b^2 and if p|b (which means p|b^2), then p|a^2. Since p is a prime, it follows that p|a.

And as I said earlier, if p|a and p|b, then (a,b)=>p, a contradiction. So p doesn't divide a or b.

I got the gist of things now. Thank you very much for your help!

8. Originally Posted by machack
Well we know p can't divide b and not a because if for 3 integers x,y, and z, if x|y+z and x|y, then x|z. In this case, p|a^2 + b^2 and if p|b (which means p|b^2), then p|a^2. Since p is a prime, it follows that p|a.

And as I said earlier, if p|a and p|b, then (a,b)=>p, a contradiction. So p doesn't divide a or b.

I got the gist of things now. Thank you very much for your help!
Of course! Slipped my mind!