Ironing out the Lucas Primality Test proof

**Deadstar** · April 16th 2010, 09:12 AM

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.

**chiph588@** · April 16th 2010, 12:41 PM

Originally Posted by Deadstar

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.

**Deadstar** · April 16th 2010, 12:43 PM

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.

**Deadstar** · April 17th 2010, 03:46 PM

Originally Posted by Deadstar

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

...

**Deadstar** · April 17th 2010, 03:52 PM

Originally Posted by Deadstar

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

**Deadstar** · April 24th 2010, 05:52 PM

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.

**chiph588@** · April 24th 2010, 06:05 PM

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.

**Deadstar** · April 24th 2010, 06:12 PM

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?

**chiph588@** · April 24th 2010, 06:16 PM

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

**Deadstar** · April 24th 2010, 06:19 PM

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.

**chiph588@** · April 24th 2010, 06:31 PM

Originally Posted by Deadstar

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

Thread: Ironing out the Lucas Primality Test proof

LinkBack

Thread Tools

Display

Ironing out the Lucas Primality Test proof

Similar Math Help Forum Discussions

The fastest way to test primality ?

Lucas-Lehmer test (proof)

Wilson's Primality Test ... what ?

program problem about primality test

The Miller-Rabin test for primality...

Search Tags