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...
On Fri, 6 Nov 2009, recoder 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...
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.
> 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.
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.
On Nov 6, 8:05 pm, recoder <kurtulmeh...@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
On 6 Nov, 09:05, recoder <kurtulmeh...@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,
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.
> If p is composite, there are more roots...
it is more complicated than that, e.g. consider the position modulo 4 or 6. "there can be more roots..." might be better
> 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...
> On Nov 6, 8:05 pm, recoder <kurtulmeh...@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?
> On 6 Kasım, 12:53, Gerry <ge...@math.mq.edu.au> wrote:
> > On Nov 6, 8:05 pm, recoder <kurtulmeh...@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 -
On Nov 6, 3:05 am, recoder <kurtulmeh...@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. 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.
> 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. > Thanks in advance...
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 <magi...@member.ams.org> wrote: > On Nov 6, 3:05 am, recoder <kurtulmeh...@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. [...]
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]
|
