# equation soluble

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Oct 20th 2013, 01:47 PM
Sonifa
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!
• Oct 20th 2013, 01:58 PM
SlipEternal
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 $\displaystyle \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?
• Oct 20th 2013, 02:59 PM
Sonifa
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)
• Oct 20th 2013, 03:11 PM
SlipEternal
Re: equation soluble
Quote:

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 $\displaystyle A = \{u \in \{0,1,2,\ldots, p-1\}\mid \exists x \in \mathbb{Z}, u \equiv x^2 \pmod{p}\}$, $\displaystyle 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 $\displaystyle |A| = |B| = \dfrac{p+1}{2}$. The set $\displaystyle \{0,1,2,\ldots,p-1\}$ has $\displaystyle p$ elements. So, $\displaystyle |A|+|B| = \dfrac{p+1}{2} + \dfrac{p+1}{2} = p+1$, but $\displaystyle |A\cup B| \le p$, hence $\displaystyle |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.
• Oct 20th 2013, 03:24 PM
Sonifa
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.
• Oct 20th 2013, 04:40 PM
SlipEternal
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).
• Oct 21st 2013, 12:52 AM
Sonifa
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???
• Oct 21st 2013, 05:35 AM
SlipEternal
Re: equation soluble
This is just a guess, but try this: Find solutions for $\displaystyle x^2+y^2+1 \equiv 0 \pmod{p_i}$ for each prime in the prime factorization of $\displaystyle m$. Then use the Chinese Remainder Theorem to find solutions in $\displaystyle m$.
• Oct 21st 2013, 05:47 AM
Sonifa
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.
• Oct 21st 2013, 06:00 AM
SlipEternal
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).
• Oct 21st 2013, 06:17 AM
Sonifa
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?
• Oct 21st 2013, 10:24 AM
SlipEternal
Re: equation soluble
I don't think that works out. Try $\displaystyle m=15$. Then for $\displaystyle x_1^2+y_1^2 +1 = 0 \pmod{3}$, you can choose $\displaystyle x_1=y_1=1$. For $\displaystyle x_2^2+y_2^2+1 = 0 \pmod{5}$, you can choose $\displaystyle x_2 = 0, y_2 = 2$. But, $\displaystyle (x_1x_2)^2 + (y_1y_2)^2 + 1 = 0+4+1 = 5 \neq 0 \pmod{15}$.

How about this: Suppose $\displaystyle m$ is odd, squarefree, and the product of $\displaystyle r$ distinct primes. Then there are at least $\displaystyle \dfrac{m+1}{2}$ distinct integers $\displaystyle u$ in $\displaystyle \{0,1,\ldots,m-1\}$ such that $\displaystyle u \equiv x^2 \pmod{m}$ for some integer $\displaystyle x$. Proof by induction. When $\displaystyle r=1$, that is the case you just proved for part (a). Suppose the proposition holds for any number of prime factors up to $\displaystyle r$. Then let $\displaystyle m$ be odd, squarefree, and the product of $\displaystyle r+1$ distinct primes. Then, given any prime factor $\displaystyle p_i$ of $\displaystyle m$, you know that $\displaystyle \dfrac{m}{p_i}$ satisfies the induction assumption, so by hypothesis, there must be $\displaystyle \dfrac{m + p_i}{2p_i}$ integers $\displaystyle u$ in $\displaystyle \{0,...,\dfrac{m}{p_i}-1\}$ such that $\displaystyle u \equiv x^2 \pmod{\dfrac{m}{p_i}}$ for some integer $\displaystyle 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.
• Oct 21st 2013, 11:57 AM
SlipEternal
Re: equation soluble
Oh, I know. Suppose you have $\displaystyle x,y$ such that $\displaystyle x^2+y^2+1 \equiv 0 \pmod{p_i}$ for all primes $\displaystyle p_i$ such that $\displaystyle p_i|m$. Then, it must be that $\displaystyle p_i | (x^2+y^2+1)$ for all such prime factors. That implies $\displaystyle m$ divides $\displaystyle x^2+y^2+1$. So, my initial thought to find solutions $\displaystyle x_i,y_i$ with $\displaystyle x_i^2+y_i^2 +1 \equiv 0 \pmod{p_i}$ and then use the Chinese Remainder Theorem to find $\displaystyle x,y$ should work.
• Oct 21st 2013, 02:04 PM
Sonifa
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.
• Oct 21st 2013, 02:18 PM
SlipEternal
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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last