# Math Help - equation soluble

1. ## equation soluble

p is an odd prime

(a) show that x^2+y^2+1=0 (mod p) is soluble

(b)
show that x^2+y^2+1=0 (mod p) is soluble for any squarefree odd m

For (a)
hint given : count the integers in {0,1,2,...,p-1} of the form x^2 modulo p and
those of the form -1-y^2 modulo p

can anyone help me ?? thanks!

2. ## Re: equation soluble

What do you need help with? Are you having trouble applying the hint? Do you have any work done that we can look at? If you are looking for a place to start, choose a couple values for p and see what is going on. For example, check out the integers in {0,1,2} of the form x^2 modulo 3 and those of the form -1-y^2 modulo 3. Try it for 5 and 7 also. Do you notice any patterns? Try to show that the number of integers of that form is greater than $\dfrac{p-1}{2}$. Then by the pigeonhole principle, there must be some x^2 and -1-y^2 that are congruent modulo p.

For (b), what is m?

3. ## Re: equation soluble

i had proved that that are (p+1)/2 integers u in {0,1,2,...,p-1} s.t. u=x^2(mod p) for some x in the previous part , i am wondering should i use this statement somewhere?? i tried some primes p but i still cannot get the connection, and for m is an odd squarfree integer(the squarfree integer is one divisible by no perfect square)

4. ## Re: equation soluble

Originally Posted by Sonifa
i had proved that that are (p+1)/2 integers u in {0,1,2,...,p-1} s.t. u=x^2(mod p) for some x in the previous part , i am wondering should i use this statement somewhere?? i tried some primes p but i still cannot get the connection, and for m is an odd squarfree integer(the squarfree integer is one divisible by no perfect square)
Let $A = \{u \in \{0,1,2,\ldots, p-1\}\mid \exists x \in \mathbb{Z}, u \equiv x^2 \pmod{p}\}$, $B = \{v \in \{0,1,2,\ldots, p-1\} \mid \exists y \in \mathbb{Z}, v \equiv -1-y^2 \pmod{p}\}$. Then, from your previous part, you have $|A| = |B| = \dfrac{p+1}{2}$. The set $\{0,1,2,\ldots,p-1\}$ has $p$ elements. So, $|A|+|B| = \dfrac{p+1}{2} + \dfrac{p+1}{2} = p+1$, but $|A\cup B| \le p$, hence $|A\cap B|\ge 1$.

For part (b), I still don't understand what m is. You don't use m in the problem's statement.

5. ## Re: equation soluble

Sorry , i made a mistake for typing. The statment should be :

show that x^2+y^2+1=0 (mod m) is soluble for any squarefree odd m.

And why is B has order (p+1)/2 . Thanks for ur part a) , I was looking for the order of B, now it,s OK for me.

6. ## Re: equation soluble

B has order (p+1)/2 because A does. If there are (p+1)/2 different integers u in {0,1,2,...,p-1} with u = x^2 (mod p), then there are (p+1)/2 different integers v = -u (mod p), and then there are (p+1)/2 different integers v' = -1-u (mod p).

7. ## Re: equation soluble

Yes, for (b) since m is squarefree odd number,then i write m as the prime factorisation m=p1p2p3.... (since no square) then by a) for every prime pi, it has a solution. I stopped here, how to deduce it has solution for their product m???

8. ## Re: equation soluble

This is just a guess, but try this: Find solutions for $x^2+y^2+1 \equiv 0 \pmod{p_i}$ for each prime in the prime factorization of $m$. Then use the Chinese Remainder Theorem to find solutions in $m$.

9. ## Re: equation soluble

but how to ensure that exist a solution for x and y s.t. x^2+y^2+1=0 (mod pi) for all i ?? if we can prove such x y exist then by chinese remaider theorem we get the resault.

10. ## Re: equation soluble

You already proved the existence of solutions for x and y (over the integers) s.t. x^2+y^2+1=0 (mod p_i) in part (a). Now, I am suggesting you find elements x_i,y_i of {0,1,2,...,p_i-1} such that x = x_i (mod p_i) and y = y_i (mod p_i) for each i. Then use the Chinese Remainder Theorem to find x (mod m) and y (mod m), and there will hopefully be a way to show that the result you get satisfies x^2+y+2+1 = 0 (mod m).

11. ## Re: equation soluble

I have the idea based on ur suggestion but i dont think it goes right.

m=p1p2p3..pr

by part (a) we have xi^2+yi^2+1=0 mod pi , now want x , y s.t. x=xi mod pi and y=yi mod pi for each i. if i take x=x1*x2*...*xr y=y1*y2*...yr then we satify our requirment ,

is my idea wrong?

12. ## Re: equation soluble

I don't think that works out. Try $m=15$. Then for $x_1^2+y_1^2 +1 = 0 \pmod{3}$, you can choose $x_1=y_1=1$. For $x_2^2+y_2^2+1 = 0 \pmod{5}$, you can choose $x_2 = 0, y_2 = 2$. But, $(x_1x_2)^2 + (y_1y_2)^2 + 1 = 0+4+1 = 5 \neq 0 \pmod{15}$.

How about this: Suppose $m$ is odd, squarefree, and the product of $r$ distinct primes. Then there are at least $\dfrac{m+1}{2}$ distinct integers $u$ in $\{0,1,\ldots,m-1\}$ such that $u \equiv x^2 \pmod{m}$ for some integer $x$. Proof by induction. When $r=1$, that is the case you just proved for part (a). Suppose the proposition holds for any number of prime factors up to $r$. Then let $m$ be odd, squarefree, and the product of $r+1$ distinct primes. Then, given any prime factor $p_i$ of $m$, you know that $\dfrac{m}{p_i}$ satisfies the induction assumption, so by hypothesis, there must be $\dfrac{m + p_i}{2p_i}$ integers $u$ in $\{0,...,\dfrac{m}{p_i}-1\}$ such that $u \equiv x^2 \pmod{\dfrac{m}{p_i}}$ for some integer $x$. Can you then use the Chinese Remainder Theorem to prove the hypothesis? I am just guessing. I don't have time at the moment to fully figure this out.

13. ## Re: equation soluble

Oh, I know. Suppose you have $x,y$ such that $x^2+y^2+1 \equiv 0 \pmod{p_i}$ for all primes $p_i$ such that $p_i|m$. Then, it must be that $p_i | (x^2+y^2+1)$ for all such prime factors. That implies $m$ divides $x^2+y^2+1$. So, my initial thought to find solutions $x_i,y_i$ with $x_i^2+y_i^2 +1 \equiv 0 \pmod{p_i}$ and then use the Chinese Remainder Theorem to find $x,y$ should work.

14. ## Re: equation soluble

I am a bit confused. by (a) we know that for pi we can we can find the solution xi yi s.t. xi^2+yi^2+1=0 mod (pi) . but when we use the chinese remainder theorem, we need to find x and y first s.t. x^2+y^2+1=o (mod pi) for each pi. My point is we should ensure x y satisfy for each congruent equation (pi) then we can use chinese remaider theorem. For me , I failed to find such x y.

15. ## Re: equation soluble

You already did prove that in part (a). That is exactly what you proved. Given any odd prime p, there exists integers x and y with x^2+y^2+1=0 (mod p). You know m is odd, so its factors will all be odd. Then, if p_i is a factor, you just in part (a) you can find a solution. You have nothing left to prove. I don't understand what issue there is with those solutions you found.

Page 1 of 2 12 Last