| |
 |
|
|
Science Forum Index » Mathematics Forum » solutions to a^2 + b^2 = x (mod p)
Page 1 of 1
|
| Author |
Message |
| Tom |
 Posted: Fri Dec 19, 2003 12:59 pm |
|
|
|
Guest
|
Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
I've determined that it is not necessarily true if p is not a prime, but
what about when it is? It seems that since a prime p has (p+1)/2
quadratic residues, the probability of choosing any a at random and
being able to solve b = sqrt(x-a^2) is .5, so there ought to be lots of
solutions. But how can you prove this?
Also, some experimentation has "convinced" me that when p is not prime,
the chances of having some x's that can't be expressed as a sum of
squares is higher when p has lots of small prime factors, then when it
has some large factors. Is there any criterion for this? |
|
|
| Back to top |
|
| Eric J. Wingler |
| Posted: Fri Dec 19, 2003 1:11 pm |
|
|
|
Guest
|
"Tom" <no@spam.here> wrote in message
news:3fe33c8a$0$9096$80265adb@spool.cs.wisc.edu...
Quote: Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
I've determined that it is not necessarily true if p is not a prime, but
what about when it is? It seems that since a prime p has (p+1)/2
quadratic residues, the probability of choosing any a at random and
being able to solve b = sqrt(x-a^2) is .5, so there ought to be lots of
solutions. But how can you prove this?
Also, some experimentation has "convinced" me that when p is not prime,
the chances of having some x's that can't be expressed as a sum of
squares is higher when p has lots of small prime factors, then when it
has some large factors. Is there any criterion for this?
What about p=5 and x=3?
_________________________________________________________
Eric J. Wingler (wingler@math.ysu.edu)
Dept. of Mathematics and Statistics
Youngstown State University
One University Plaza
Youngstown, OH 44555-0001
330-941-1817 |
|
|
| Back to top |
|
| Timothy Murphy |
| Posted: Fri Dec 19, 2003 1:17 pm |
|
|
|
Guest
|
Eric J. Wingler wrote:
Quote: Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
What about p=5 and x=3?
2^2 + 2^2 = 3 mod 5 ?
--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland |
|
|
| Back to top |
|
| Tom |
| Posted: Fri Dec 19, 2003 1:20 pm |
|
|
|
Guest
|
When p=5, and x=3, a solution is 2^2+2^2=3 (mod 5)
Eric J. Wingler wrote:
Quote: "Tom" <no@spam.here> wrote in message
news:3fe33c8a$0$9096$80265adb@spool.cs.wisc.edu...
Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
I've determined that it is not necessarily true if p is not a prime, but
what about when it is? It seems that since a prime p has (p+1)/2
quadratic residues, the probability of choosing any a at random and
being able to solve b = sqrt(x-a^2) is .5, so there ought to be lots of
solutions. But how can you prove this?
Also, some experimentation has "convinced" me that when p is not prime,
the chances of having some x's that can't be expressed as a sum of
squares is higher when p has lots of small prime factors, then when it
has some large factors. Is there any criterion for this?
What about p=5 and x=3?
_________________________________________________________
Eric J. Wingler (wingler@math.ysu.edu)
Dept. of Mathematics and Statistics
Youngstown State University
One University Plaza
Youngstown, OH 44555-0001
330-941-1817
|
|
|
| Back to top |
|
| Edgar Binder |
| Posted: Fri Dec 19, 2003 1:25 pm |
|
|
|
Guest
|
Tom wrote:
Quote: Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
I think there exists a somehow stronger (related) result:
for every a, x and for every prime p, there exists b such that:
either: a - b ^ 2 = x (mod p)
or: a + b ^ 2 = x (mod p)
This property is quite important for quadratic sonding for hash tables
Using this, it should be easy find solutions to a^2 + b^2 = x (mod p).
--
Edgar |
|
|
| Back to top |
|
| Timothy Murphy |
| Posted: Fri Dec 19, 2003 1:27 pm |
|
|
|
Guest
|
Tom wrote:
Quote: Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
It is true.
One way to see this is to note that the quadratic residues mod p
form a subgroup Q < (Z/p)* of index 2.
If S = {x in (Z/p)*: x = a^2 + b^2 mod p} < (Z/p)*
then QS = S, ie q in Q, s in S => qs in S.
So S is a union of Q-cosets,
and is therefore Q or the whole of (Z/p)*.
But if S = Q then s in S => 1 + s in S => 1 + ... + 1 in S.
--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland |
|
|
| Back to top |
|
| Eric J. Wingler |
| Posted: Fri Dec 19, 2003 1:36 pm |
|
|
|
Guest
|
"Timothy Murphy" <tim@birdsnest.maths.tcd.ie> wrote in
message news:ZgHEb.1516$HR.4336@news.indigo.ie...
Quote: Eric J. Wingler wrote:
Is it true that, for every prime p and every 0<=x<p,
that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
What about p=5 and x=3?
2^2 + 2^2 = 3 mod 5 ?
Duh! I should be more careful. It seems likely that this
is true because it is likely that you could always find a
number n such that x+np is a product of primes that are
congruent to 1 modulo 4 or equal to 2.
_________________________________________________________
Eric J. Wingler (wingler@math.ysu.edu)
Dept. of Mathematics and Statistics
Youngstown State University
One University Plaza
Youngstown, OH 44555-0001
330-941-1817 |
|
|
| Back to top |
|
| Edgar Binder |
| Posted: Fri Dec 19, 2003 1:36 pm |
|
|
|
Guest
|
Edgar Binder wrote:
Quote: This property is quite important for quadratic sonding for hash tables
Sorry, english is not my primary language.
Here's the correct name: "quadratic probing".
And here a proof (although only for the a + b ^ 2 = x (mod p) ):
http://condor.depaul.edu/~ntomuro/courses/417/notes/qp.html
--
Edgar |
|
|
| Back to top |
|
| Erick Bryce Wong |
| Posted: Fri Dec 19, 2003 8:23 pm |
|
|
|
Guest
|
Edgar Binder <forename@softyx.com> wrote:
Quote: I think there exists a somehow stronger (related) result:
for every a, x and for every prime p, there exists b such that:
either: a - b ^ 2 = x (mod p)
or: a + b ^ 2 = x (mod p)
This is only true when p=2 or p == 3 (mod 4). For instance, there's no
solution for p=5, a=1, x=3.
-- Erick |
|
|
| Back to top |
|
| JHS |
| Posted: Fri Dec 19, 2003 8:26 pm |
|
|
|
Guest
|
Yes, this is true. Here's a quick proof.
Theorem: Let p be prime. For every value of x, there are integers a
and b so that
a^2 + b^2 = x (mod p).
Proof: Look at the set
S = { a^2 (mod p) : 0 <= a <= (p-1)/2 }
The set S contains (p+1)/2 different elements, since a nonzero square
k^2 has the two square roots mod p, namely k and p-k, and exactly one
of them is in the interval between 1 and (p-1)/2.
Now fix any value for x and look at the set
T = { x - b^2 (mod p) : 0 <= b <= (p-1)/2 }.
The same reasoning shows that T contains (p+1)/2 distinct elements.
Thus S and T each contain (p+1)/2 distinct elements mod p. But there
are only p different numbers mod p, so by the pigeonhole principle, S
and T have an element y in common. That element y is equal to A^2 for
some A, since y is in S, and y is equal to x-B^2 for some B, since y
is in T. Therefore
A^2 = x - B^2,
which gives you your desired solution.
By the Chinese Remainder Theorem, this implies that
a^2 + b^2 = x (mod n)
always has a solution if n is a product of _distinct_ primes. So for
your second question, primes that appear in n to the first power don't
affect whether or not there is a solution. That may explain some of
what you've found.
JoeS
Tom <no@spam.here> wrote in message news:<3fe33c8a$0$9096$80265adb@spool.cs.wisc.edu>...
Quote: Is it true that, for every prime p and every 0<=x<p, that there exists a
solution a,b such that a^2+b^2=x (mod p) ?
I've determined that it is not necessarily true if p is not a prime, but
what about when it is? It seems that since a prime p has (p+1)/2
quadratic residues, the probability of choosing any a at random and
being able to solve b = sqrt(x-a^2) is .5, so there ought to be lots of
solutions. But how can you prove this?
Also, some experimentation has "convinced" me that when p is not prime,
the chances of having some x's that can't be expressed as a sum of
squares is higher when p has lots of small prime factors, then when it
has some large factors. Is there any criterion for this? |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Fri Oct 10, 2008 5:56 pm
|
|