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

Primality of generalized Proth numbers

Expand Messages
  • hl59126
    Define a q-residue modulo n as follows: An integer a is a q-residue modulo n if and only if it exists an integer b such as b^(2^q)=a mod n Obviously if q=1
    Message 1 of 2 , Jan 4, 2005
    • 0 Attachment
      Define a q-residue modulo n as follows:
      An integer a is a q-residue modulo n if and only if it exists an
      integer b such as b^(2^q)=a mod n
      Obviously if q=1 then we define the quadractic residues.

      Now, consider the numbers of the form n=k*2^q+1, q and k are
      unconstrained. Since Proth number imposes k<2^q, we call these
      numbers generalized Proth numbers.

      With these definitions we have the following result:
      n=k*2^q+1 is prime if and only if there exist exactly k-1 integers
      comprised between 2 and n-1 who are q-residue modulo n.

      I'm not aware if this result is already known.
      Thanks for any comments.
    • 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 2 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.