# Thread: Ironing out the Lucas Primality Test proof

1. ## 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.

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.

3. Originally Posted by chiph588@
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.

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$.

...

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)$

6. 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.

...

Oh and wikipedia doesn't help me here. Not in depth enough.

7. 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.

8. Ok, this,

Originally Posted by chiph588@
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,

Originally Posted by chiph588@
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?

9. There's a theorem that says $\displaystyle a^r\equiv1\bmod{n} \iff \text{ord}_n(a)\mid r$.

10. Originally Posted by chiph588@
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.

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$.