 |
|
| Science Forum Index » Mathematics Forum » square root modulo composite number distribution... |
|
Page 1 of 1 |
|
| Author |
Message |
| recoder... |
 Posted: Thu Nov 05, 2009 11:05 pm |
|
|
|
Guest
|
If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
If p is composite, there are more roots...
What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
In my case p is a odd composite number.
Thanks in advance... |
|
|
| Back to top |
|
|
|
| Gerry... |
| Posted: Fri Nov 06, 2009 12:53 am |
|
|
|
Guest
|
On Nov 6, 8:05 pm, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
[quote]If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
If p is composite, there are more roots...
[/quote]
If p is composite, don't call it p, you'll just confuse people.
Call it n.
[quote]What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
[/quote]
Do you really mean between 0 and a? There's no reason to think
that any of the square roots of a will be between 0 and a.
Perhaps you're asking about the distribution between 0 and n?
But even in the prime case, there's not all that much you can
say about the distribution of the square roots of a, except
that if one of the is r, then the other is p - r. And that
symmetry holds in the non-prime case.
Or maybe all you're asking about is the *number* of square
roots of a?
--
GM |
|
|
| Back to top |
|
|
|
| Henry... |
| Posted: Fri Nov 06, 2009 12:54 am |
|
|
|
Guest
|
On 6 Nov, 09:05, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
[quote]If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
[/quote]
I assume you mean that if for example modulo 7, 1 has the roots 1 and
6, while 2 has the roots 2 and 3, and 4 has the roots 2 and 5; except
that 0 only has one root if p is prime, while modulo 2 then both 0 and
1 only have one root each.
[quote]If p is composite, there are more roots...
[/quote]
it is more complicated than that, e.g. consider the position modulo 4
or 6. "there can be more roots..." might be better
[quote]What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
In my case p is a odd composite number.
Thanks in advance...
[/quote]
You might find something at http://www.research.att.com/~njas/sequences/A000224
This includes a formula for the number of squares modulo n, and this
can be less than n/2. Note that it is a multiplicative function |
|
|
| Back to top |
|
|
|
| recoder... |
| Posted: Fri Nov 06, 2009 1:28 am |
|
|
|
Guest
|
On 6 Kasım, 12:53, Gerry <ge... at (no spam) math.mq.edu.au> wrote:
[quote]On Nov 6, 8:05Â pm, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
If p is composite, there are more roots...
If p is composite, don't call it p, you'll just confuse people.
Call it n.
What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
Do you really mean between 0 and a? There's no reason to think
that any of the square roots of a will be between 0 and a.
Perhaps you're asking about the distribution between 0 and n?
But even in the prime case, there's not all that much you can
say about the distribution of the square roots of a, except
that if one of the is r, then the other is p - r. And that
symmetry holds in the non-prime case.
Or maybe all you're asking about is the *number* of square
roots of a?
--
GM
[/quote]
My bad, I ment the square roots of a mod n, located between 0 and n.
If there are more than 2 roots, does the Symmetry n-r hold for every
root? |
|
|
| Back to top |
|
|
|
| Pubkeybreaker... |
| Posted: Fri Nov 06, 2009 3:04 am |
|
|
|
Guest
|
On Nov 6, 6:28Â am, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
[quote]On 6 Kasım, 12:53, Gerry <ge... at (no spam) math.mq.edu.au> wrote:
On Nov 6, 8:05Â pm, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
If p is composite, there are more roots...
If p is composite, don't call it p, you'll just confuse people.
Call it n.
What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
Do you really mean between 0 and a? There's no reason to think
that any of the square roots of a will be between 0 and a.
Perhaps you're asking about the distribution between 0 and n?
But even in the prime case, there's not all that much you can
say about the distribution of the square roots of a, except
that if one of the is r, then the other is p - r. And that
symmetry holds in the non-prime case.
Or maybe all you're asking about is the *number* of square
roots of a?
--
GM
My bad, I ment the square roots of a mod n, located between 0 and n.
If there are more than 2 roots, does the Symmetry n-r hold for every
root?- Hide quoted text -
[/quote]
-1 * -1 = +1 |
|
|
| Back to top |
|
|
|
| William Elliot... |
| Posted: Fri Nov 06, 2009 5:33 am |
|
|
|
Guest
|
On Fri, 6 Nov 2009, recoder wrote:
[quote]If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
If p is composite, there are more roots...
[/quote]
Also, there may not be any.
Let p = 12. Table of Squares
1 2 3 4 5 6 7 8 9 10 11
1 4 9 4 1 0 1 4 9 4 1
Only 1,4, 9 and 0 have square roots. The others do not.
Let p = 6.
1 2 3 4 5
1 4 3 4 1
Notice there's only one square root of 3.
Let p = 4. Observe the following:
2 and 3 do not have square roots
0 and 2 are both square roots of 0
When p is prime, only 0 is a square root of 0.
[quote]What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
In my case p is a odd composite number.
[/quote]
Table of squares for p = 9.
1 2 3 4 5 6 7 8
1 4 0 7 7 0 4 1
Only 1, 4, 7 and 0 have square roots while
2, 3, 5, 6 and 8 do not have square roots.
Table of squares for p = 15
1 2 3 4 5 6 7
1 4 9 1 10 6 4
Only 1, 4, 9 and 10 have square roots. The others do not. |
|
|
| Back to top |
|
|
|
| Arturo Magidin... |
| Posted: Fri Nov 06, 2009 7:09 am |
|
|
|
Guest
|
On Nov 6, 3:05 am, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
[quote]If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
[/quote]
Not always. x^2 = 1 (mod 2) has one and only one solution modulo 2.
And x^2=0 (mod p) has one and only one solution modulo p for each
prime p.
*But* if p>2 and a=/= 0 (mod p), then x^2=a (mod p) has either no
solutions or two solutions.
[quote]If p is composite, there are more roots...
[/quote]
Sometimes.
[quote]What I wonder is are there any rules for the distribution of the
square roots between 0 and a.
In my case p is a odd composite number.
Thanks in advance...
[/quote]
Suppose that n is an odd composite number, and a is an integer, 0 < a
< n. Factor n into primes, n = p_1^{a_1} *... * p_r^{a_r}.
If x^2 = a (mod n) has at least one solution, then x^2 = a (mod p_i^
{a_i}) has at least one solution for each i; if gcd(a,n)=1, then x^2=a
(mod p_i^{a_i}) has exactly two solutions, which can be obtained by
finding solutions to x^2 = a (mod p) and then lifting them using
Hensel's Lemma.
If you let s_{i1} and s_{i2} be the two solutions modulo p_i^{a_i},
then the Chinese Remainder Theorem tells you that for every function j:
{1,...,n}-->{1,2}, there is one and only one x modulo n such that x=s_
{ij(i)} mod (p_i^{a_i}); this x will necessarily be a solution to
x^2=a (mod n); conversely, any solution to x^2=a (mod n) must reduce
to a choice of solutions modulo each p_i^{a_i}.
Thus, you will have 2^r distinct solutions modulo n when gcd(a,n)=1
and there is at least one solution.
If gcd(a,n)>1, some of the congruences above reduce to x^2 = 0 (mod
p_i), which have only one solution. But x^2 = 0 (mod p_i^2) has more
solutions: you have p solutions, 0, p, 2p, 3p, ..., (p-1)p. And so on.
In general, a solution to x^2=0 (mod p_i^{a_i}) is either 0, or of
the form tp_i^j with gcd(t,p)=1 and 2j>= a_i. You would need to count
these, for each prime that divides gcd(a,n), and then use the Chinese
Remainder Theorem as above.
--
Arturo Magidin |
|
|
| Back to top |
|
|
|
| Bill Dubuque... |
| Posted: Fri Nov 06, 2009 3:16 pm |
|
|
|
Guest
|
Arturo Magidin <magidin at (no spam) member.ams.org> wrote:
[quote]On Nov 6, 3:05 am, recoder <kurtulmeh... at (no spam) gmail.com> wrote:
If there exists a number x such that x^2 = a (mod p)
then x is called a square root of a (mod p)
If p is a prime , there are 2 roots,
Not always. x^2 = 1 (mod 2) has one and only one solution modulo 2.
x^2=0 (mod p) has one and only one solution modulo p for each prime p.
*But* if p>2 and a=/= 0 (mod p), then x^2=a (mod p) has either no
solutions or two solutions.
If p is composite, there are more roots...
Sometimes.
What I wonder is are there any rules for the distribution of the
square roots between 0 and a. In my case p is a odd composite number.
Suppose that n is an odd composite number, and a is an integer, 0 < a
n. Factor n into primes, n = p_1^{a_1} *... * p_r^{a_r}.
If x^2 = a (mod n) has at least one solution, then x^2 = a (mod p_i^
{a_i}) has at least one solution for each i; if gcd(a,n)=1, then x^2=a
(mod p_i^{a_i}) has exactly two solutions, which can be obtained by
finding solutions to x^2 = a (mod p) and then lifting them using
Hensel's Lemma. [...]
[/quote]
Actually Hensel's Lemma (Newton iteration) isn't needed since there's
a simple formula to lift Z/pZ sqrts to Z/(p^e)Z [due to Tonelli iirc]
LEMMA yy = a (mod p) => xx = a (mod p^e)
for x = y^c a^d, c = p^(e-1), d = ((p-2)c+1)/2
PROOF xx = a^c a^((p-2)c+1)
= a^((p-1)c) a
= a via (p-1)c = phi(p^e)
--Bill Dubuque |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sun Nov 29, 2009 5:02 pm
|
|