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

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.

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

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.

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

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

...

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

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

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

8. Ok, this,

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

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

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

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

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