Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Jack Brennen
    ... 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.