Results 1 to 11 of 11

Math Help - Ironing out the Lucas Primality Test proof

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Ironing out the Lucas Primality Test proof

    As I was typing this out I realized I had more questions than I thought...

    Theorem


    Let n > 1, and suppose that for every prime factor q of n-1 there is an integer a such that,

    a^{n-1} \equiv 1 (\textrm{mod } n)<br />

    but,

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } n)

    Then n is prime.

    Proof

    We want to show that \varphi(n) = n-1 which implies that n is prime.

    Consider the group \mathbf{Z}_n^X = \big{\{}a:1 \leq a < n, \, \gcd(a,n) = 1 \big{\}} where \#\mathbf{Z}_n^X= \varphi(n).

    We look at the subgroup H of \mathbf{Z}_n^X generated by all a_q's. (Does this simply mean all the q values that divide n-1)

    As a_q^{n-1} = \varphi(n) (My notes are unclear here so correct me if that part is wrong, I suspect it is), the exponent of H divides n-1 (What exponent?).

    But the exponent can't be a proper factor of n-1 as,

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } H) (Should H be there? I don't fully understand that conclusion).

    So the exponent = n-1.

    But then exponent|#H and \#H|\#Z = \varphi(n) so n-1|\varphi(n).

    As \varphi(n) \leq n-1, \varphi(n) = n-1. Q.E.D.


    Lines 4-7 of the proof is what I'm not sure about.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Deadstar View Post
    As I was typing this out I realized I had more questions than I thought...

    Theorem


    Let n > 1, and suppose that for every prime factor q of n-1 there is an integer a such that,

    a^{n-1} \equiv 1 (\textrm{mod } n)<br />

    but,

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } n)

    Then n is prime.

    Proof

    We want to show that \varphi(n) = n-1 which implies that n is prime.

    Consider the group \mathbf{Z}_n^X = \big{\{}a:1 \leq a < n, \, \gcd(a,n) = 1 \big{\}} where \#\mathbf{Z}_n^X= \varphi(n).

    We look at the subgroup H of \mathbf{Z}_n^X generated by all a_q's. (Does this simply mean all the q values that divide n-1)

    As a_q^{n-1} = \varphi(n) (My notes are unclear here so correct me if that part is wrong, I suspect it is), the exponent of H divides n-1 (What exponent?).

    But the exponent can't be a proper factor of n-1 as,

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } H) (Should H be there? I don't fully understand that conclusion).

    So the exponent = n-1.

    But then exponent|#H and \#H|\#Z = \varphi(n) so n-1|\varphi(n).

    As \varphi(n) \leq n-1, \varphi(n) = n-1. Q.E.D.


    Lines 4-7 of the proof is what I'm not sure about.
    Wikipedia is always a good place to check.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by chiph588@ View Post
    Wikipediais always a good place to check.
    It's not exactly much of a proof though...

    doesn't actually clear up any of the parts I highlighted.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Deadstar View Post
    As I was typing this out I realized I had more questions than I thought...

    Theorem


    Let n > 1, and suppose that for every prime factor q of n-1 there is an integer a such that,

    a^{n-1} \equiv 1 (\textrm{mod } n)<br />

    but,

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } n)

    Then n is prime.

    Proof

    We want to show that \varphi(n) = n-1 which implies that n is prime.

    Consider the group \mathbf{Z}_n^X = \big{\{}a:1 \leq a < n, \, \gcd(a,n) = 1 \big{\}} where \#\mathbf{Z}_n^X= \varphi(n).

    We look at the subgroup H of \mathbf{Z}_n^X generated by all a_q's. (Does this simply mean all the q values that divide n-1) (1)

    As a_q^{n-1} = \varphi(n) (My notes are unclear here so correct me if that part is wrong, I suspect it is) (2), the exponent of H divides n-1 (What exponent?) (3).

    But the exponent can't be a proper factor of n-1 as,

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } H) (Should H be there? I don't fully understand that conclusion). (4)

    So the exponent = n-1.

    But then exponent|#H and \#H|\#Z = \varphi(n) so n-1|\varphi(n).

    As \varphi(n) \leq n-1, \varphi(n) = n-1. Q.E.D.


    Lines 4-7 of the proof is what I'm not sure about.

    Some of my thoughts...

    1) Yes I think so.

    2) I think that is correct. If I'm right in saying... The order of an element of a group divides the order of the group. So if, for some a_q, the order of a_q = n-1, then the order of the group is n-1.
    In this case the group is just \varphi(n) which we want to show is equal to n-1.

    3) The exponent is the order of the group.

    4) I still don't understand the conclusion. How does

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } n)

    show the order is n-1.

    ...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Deadstar View Post
    Some of my thoughts...

    1) Yes I think so.

    2) I think that is correct. If I'm right in saying... The order of an element of a group divides the order of the group. So if, for some a_q, the order of a_q = n-1, then the order of the group is n-1.
    In this case the group is just \varphi(n) which we want to show is equal to n-1.

    3) The exponent is the order of the group.

    4) I still don't understand the conclusion. How does

    a^{\tfrac{n-1}{q}} \not\equiv 1 (\textrm{mod } n)

    show the order is n-1.

    ...
    Does (4) have anything to do with Eulers Theorem?

    a^{\varphi(n)} \equiv 1 \textrm{ (mod } n)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    I'm gonna have to bump this as I still do not understand this test.

    Is my thoughts about (1) right? If so why is this the case? Why consider only these values?

    What is the significance of the

    a^{(n-1)/q} \not\equiv 1 (\textrm{ mod } n) part... I just do not understand what this proves.


    ...


    The more I think about this the more confusing it's becoming.

    Oh and wikipedia doesn't help me here. Not in depth enough.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    If  a^{(n-1)/q}\not\equiv1\bmod{n} and  a^{n-1}\equiv1\bmod{n} , then this tells us that  \text{ord}(a)=n-1 .

    But since  a\in(\mathbb{Z}/n\mathbb{Z})^\times \implies \text{ord}(a)\mid |(\mathbb{Z}/n\mathbb{Z})^\times| = \phi(n) .

    So  \phi(n)=d\cdot(n-1) , but  \phi(n)\leq n-1 \implies d=1 \implies \phi(n)=n-1 \implies n is prime.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Ok, this,

    Quote Originally Posted by chiph588@ View Post
    But since  a\in(\mathbb{Z}/n\mathbb{Z})^\times \implies \text{ord}(a)\mid |(\mathbb{Z}/n\mathbb{Z})^\times| = \phi(n) .

    So  \phi(n)=d\cdot(n-1) , but  \phi(n)\leq n-1 \implies d=1 \implies \phi(n)=n-1 \implies n is prime.
    is fine. I understand that part. (I say that, I probably don't, the more I look at number theory the less sense it makes).

    This,

    Quote Originally Posted by chiph588@ View Post
    If  a^{(n-1)/q}\not\equiv1\bmod{n} and  a^{n-1}\equiv1\bmod{n} , then this tells us that  \text{ord}(a)=n-1 .
    I don't.

    I think it must be mildly trivial though since that's basically what's stated in the proof I was given as well. What am I not seeing?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    There's a theorem that says  a^r\equiv1\bmod{n} \iff \text{ord}_n(a)\mid r .
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by chiph588@ View Post
    There's a theorem that says  a^r\equiv1\bmod{n} \iff \text{ord}_n(a)\mid r .
    THIS!

    This is something I cannot find in my notes and have not seen. Be right back looking it up and finding proofs. Thanks for that.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Deadstar View Post
    THIS!

    This is something I cannot find in my notes and have not seen. Be right back looking it up and finding proofs. Thanks for that.
    Let  b=\text{ord}_n(a) .

    One way of the proof is easy:  b\mid r\implies r=d\cdot b so  a^r = \left(a^b\right)^d\equiv 1^d=1\bmod{n} .

    Now assume  a^r\equiv 1\bmod{n} . Let  r=k\cdot b +d where  0\leq d<b .

    We then have  1\equiv a^r = \left(a^b\right)^k\cdot a^d \equiv a^d \bmod{n} . But  a^d\equiv1\bmod{n} \text{ and } d<\text{ord}_n(a)\implies d=0 \implies r=k\cdot b \implies \text{ord}_n(a)\mid r .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The fastest way to test primality ?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 9th 2011, 10:00 AM
  2. Lucas-Lehmer test (proof)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 21st 2010, 06:26 PM
  3. Wilson's Primality Test ... what ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 9th 2010, 07:44 AM
  4. program problem about primality test
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 12th 2010, 12:02 AM
  5. The Miller-Rabin test for primality...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 11th 2008, 03:24 PM

Search Tags


/mathhelpforum @mathhelpforum