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

Re: Primality of generalized Proth numbers

Expand Messages
  • Payam Samidoost
    hleleu ... Define a 2^n-residue modulo m as follows: An integer a is a 2^n-residue modulo m if and only if it exists an integer b such as b^(2^n)=a mod m
    Message 1 of 2 , Jan 5, 2005
    • 0 Attachment
      hleleu
      Rewriting your question in a more readable form with some comments:

      >>>>>
      Define a 2^n-residue modulo m as follows:
      An integer a is a 2^n-residue modulo m if and only if it exists an
      integer b such as b^(2^n)=a mod m
      Obviously if n=1 then we define the quadractic residues.
      [not a new definition]

      Now, consider the numbers of the form n=k*2^n+1, n and k are
      unconstrained. Since Proth number imposes k<2^n, we call these
      numbers generalized Proth numbers.
      [better be named an arbitrary odd number]

      With these definitions we have the following result:
      p=k*2^n+1 is prime if and only if there exist exactly k [that is gcd
      (p-1,2^n)] integers
      comprised between 1 and p-1 who are 2^n-residue modulo p.
      <<<<<

      > I'm not aware if this result is already known.

      It is a special case of a very well known theorem named Euler's
      Criterion for solvability of the equation x^n=a(mod p). This
      equation is solvable iff a^((p-1)/d)=1(mod p) where d=gcd(p-1,n). If
      the equation is solvable then it has exactly d solutions.

      Payam
    Your message has been successfully submitted and would be delivered to recipients shortly.