Results 1 to 2 of 2

Math Help - Tough prime testing question

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    9

    Tough prime testing question

    If
    n > 1 is an integer and for each prime factor q of n-1 there is an an integer a such that and a^(n-1)=1 (mod n),
    but a^((n-1)/q) != 1 (mod n), then n is prime.


    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by kobulingam View Post
    If n > 1 is an integer and for each prime factor q of n-1 there is an an integer a such that and a^(n-1)=1 (mod n),

    but a^((n-1)/q) != 1 (mod n), then n is prime.
    I don't see a question.
    That is a statement of the Lucas primality test.
    An explanation for the correctness of that is here: Lucas primality test - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime testing with base 2 test.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 10th 2011, 02:47 PM
  2. Tough question
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: April 2nd 2010, 12:36 PM
  3. tough question
    Posted in the Algebra Forum
    Replies: 15
    Last Post: September 4th 2009, 09:02 AM
  4. another tough integral question..
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 20th 2009, 09:34 PM
  5. Needs help on a tough question
    Posted in the Calculus Forum
    Replies: 3
    Last Post: July 25th 2006, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum