Re: [PrimeNumbers] Re: The largest residue of n^2 mod p

Expand Messages
• ... Basically, the p-r values are the *smallest* numbers such that the *negative* of the number is a square mod p. So consider the case where a composite
Message 1 of 3 , Sep 16, 2012
• 0 Attachment
On 9/16/2012 8:14 PM, Mark wrote:
>
> Here it is again:
>
> The largest residue of n^2 mod p ; p is prime
>
> By observation it appears all the p-r values are 1 or a prime. Or is it
> the law of small numbers at work?
>

Basically, the p-r values are the *smallest* numbers such that the *negative*
of the number is a square mod p.

So consider the case where a composite number (let's say 6) meets the
requirement; i.e., -6 is a square mod p.

Note that it is impossible for -1, -2, and -3 to all be non-square residues
modulo p, but for -6 to be a square. This is because the product of three
non-square residues is a non-square residue; if -1, -2, and -3 are all
non-square residues, so is -6.

You can fill in the blanks from there...
Your message has been successfully submitted and would be delivered to recipients shortly.