square root modulo composite number distribution - sci.math.num-analysis

Message from discussion square root modulo composite number distribution

William Elliot

View profile

More options Nov 6 2009, 11:33 am

Newsgroups: sci.math.num-analysis, sci.math

From: William Elliot <ma...@rdrop.remove.com>

Date: Fri, 6 Nov 2009 02:33:03 -0800

Local: Fri, Nov 6 2009 11:33 am

Subject: Re: square root modulo composite number distribution

  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

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.

Forward