Results 1 to 11 of 11

Thread: 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 $\displaystyle n > 1$, and suppose that for every prime factor $\displaystyle q$ of $\displaystyle n-1$ there is an integer $\displaystyle a$ such that,

    $\displaystyle a^{n-1} \equiv 1 (\textrm{mod } n)
    $

    but,

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

    Then $\displaystyle n$ is prime.

    Proof

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

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

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

    As $\displaystyle 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 $\displaystyle H$ divides $\displaystyle n-1$ (What exponent?).

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

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

    So the exponent = $\displaystyle n-1$.

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

    As $\displaystyle \varphi(n) \leq n-1$, $\displaystyle \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 $\displaystyle n > 1$, and suppose that for every prime factor $\displaystyle q$ of $\displaystyle n-1$ there is an integer $\displaystyle a$ such that,

    $\displaystyle a^{n-1} \equiv 1 (\textrm{mod } n)
    $

    but,

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

    Then $\displaystyle n$ is prime.

    Proof

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

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

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

    As $\displaystyle 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 $\displaystyle H$ divides $\displaystyle n-1$ (What exponent?).

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

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

    So the exponent = $\displaystyle n-1$.

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

    As $\displaystyle \varphi(n) \leq n-1$, $\displaystyle \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 $\displaystyle n > 1$, and suppose that for every prime factor $\displaystyle q$ of $\displaystyle n-1$ there is an integer $\displaystyle a$ such that,

    $\displaystyle a^{n-1} \equiv 1 (\textrm{mod } n)
    $

    but,

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

    Then $\displaystyle n$ is prime.

    Proof

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

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

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

    As $\displaystyle 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 $\displaystyle H$ divides $\displaystyle n-1$ (What exponent?) (3).

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

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

    So the exponent = $\displaystyle n-1$.

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

    As $\displaystyle \varphi(n) \leq n-1$, $\displaystyle \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 $\displaystyle a_q$, the order of $\displaystyle a_q = n-1$, then the order of the group is $\displaystyle n-1$.
    In this case the group is just $\displaystyle \varphi(n)$ which we want to show is equal to $\displaystyle n-1$.

    3) The exponent is the order of the group.

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

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

    show the order is $\displaystyle 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 $\displaystyle a_q$, the order of $\displaystyle a_q = n-1$, then the order of the group is $\displaystyle n-1$.
    In this case the group is just $\displaystyle \varphi(n)$ which we want to show is equal to $\displaystyle n-1$.

    3) The exponent is the order of the group.

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

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

    show the order is $\displaystyle n-1$.

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

    $\displaystyle 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

    $\displaystyle 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 $\displaystyle a^{(n-1)/q}\not\equiv1\bmod{n} $ and $\displaystyle a^{n-1}\equiv1\bmod{n} $, then this tells us that $\displaystyle \text{ord}(a)=n-1 $.

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

    So $\displaystyle \phi(n)=d\cdot(n-1) $, but $\displaystyle \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 $\displaystyle a\in(\mathbb{Z}/n\mathbb{Z})^\times \implies \text{ord}(a)\mid |(\mathbb{Z}/n\mathbb{Z})^\times| = \phi(n) $.

    So $\displaystyle \phi(n)=d\cdot(n-1) $, but $\displaystyle \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 $\displaystyle a^{(n-1)/q}\not\equiv1\bmod{n} $ and $\displaystyle a^{n-1}\equiv1\bmod{n} $, then this tells us that $\displaystyle \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 $\displaystyle 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 $\displaystyle 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 $\displaystyle b=\text{ord}_n(a) $.

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

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

    We then have $\displaystyle 1\equiv a^r = \left(a^b\right)^k\cdot a^d \equiv a^d \bmod{n} $. But $\displaystyle 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: Dec 9th 2011, 09:00 AM
  2. Lucas-Lehmer test (proof)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 21st 2010, 05:26 PM
  3. Wilson's Primality Test ... what ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 9th 2010, 06:44 AM
  4. program problem about primality test
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 11th 2010, 11:02 PM
  5. The Miller-Rabin test for primality...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Dec 11th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum