The little theorem and its implication of coprimality.

[bamuelsanks]

Hi guys.

I'm rather new to number theory, and as part of an assignment I have been learning about various different primality tests.
One of these tests is the Lucas primality test.
As part of the reasoning behind the test, wikipedia states:
"If [$a^{n-1} \equiv 1 \textrm{ (mod }n\textrm{)}$] holds for a, we can deduce that a and n are coprime".
Would anybody be able to help me understand why this is true?

Thanks,
SB

 

[chisigma]

A theorem due to Leonhard Euler...

http://mathworld.wolfram.com/EulersTotientTheorem.html

... establishes that for all a coprime to n is...

$\displaystyle a^{\varphi (n)} \equiv 1\ \text{mod}\ n$ (1)

... where $\varphi(n)$ is the 'Euler's Totiens Function'. Now if n is prime is $\displaystyle \varphi(n)=n-1$...

Kind regards

$\chi$ $\sigma$

 

[alexmahone]

A theorem due to Leonhard Euler...

http://mathworld.wolfram.com/EulersTotientTheorem.html

... establishes that for all a coprime to n is...

$\displaystyle a^{\varphi (n)} \equiv 1\ \text{mod}\ n$ (1)

... where $\varphi(n)$ is the 'Euler's Totiens Function'. Now if n is prime is $\displaystyle \varphi(n)=n-1$...

Kind regards

$\chi$ $\sigma$

That is the converse of what the OP is trying to prove. Secondly, the OP does not say that $n$ is prime.

 

[chisigma]

What is written by Alexmahone is true. The converse of the Euler's totient theorem established that if...

$\displaystyle a^{\varphi(n)} \equiv 1\ \text{mod}\ n$ (1)

... then a and n are coprime. The important point however is that the identity $\displaystyle \varphi(n)=n-1$ holds only for n prime...

Kind regards

$\chi$ $\sigma$

 

[alexmahone]

What is written by Alexmahone is true. The converse of the Euler's totient theorem established that if...

$\displaystyle a^{\varphi(n)} \equiv 1\ \text{mod}\ n$ (1)

... then a and n are coprime. The important point however is that the identity $\displaystyle \varphi(n)=n-1$ holds only for n prime...

Kind regards

$\chi$ $\sigma$

Honestly, I don't think you've proved anything. If you think you have, could you please write your proof out?

To be precise, I don't see how you went from $a^{n-1}\equiv 1\pmod{n}$ to $a^{\phi(n)}\equiv 1\pmod{n}$. Note that $n$ need not be prime.

 

[Opalg]

Hi guys.

I'm rather new to number theory, and as part of an assignment I have been learning about various different primality tests.
One of these tests is the Lucas primality test.
As part of the reasoning behind the test, wikipedia states:
"If [$a^{n-1} \equiv 1 \textrm{ (mod }n\textrm{)}$] holds for a, we can deduce that a and n are coprime".
Would anybody be able to help me understand why this is true?

If $a^{n-1} \equiv 1 \pmod n$ then $a^{n-1} = 1+kn$ for some integer $k$. Thus $a^{n-1}$ and $n$ cannot have any prime common factor. But the prime factors of $a^{n-1}$ are the same as those of $a$. Hence $a$ and $n$ are coprime.

 

[alexmahone]

If $a^{n-1} \equiv 1 \pmod n$ then $a^{n-1} = 1+kn$ for some integer $k$. Thus $a^{n-1}$ and $n$ cannot have any prime common factor. But the prime factors of $a^{n-1}$ are the same as those of $a$. Hence $a$ and $n$ are coprime.

You didn't use the fact that the exponent of $a$ is $n-1$, so is it true for any exponent?

 

[bamuelsanks]

Thanks for the quick replies!
I understand it now, though I couldn't quite follow chisigma's response unfortunately.
Apologies for not making clear that $n$ was not necessarily prime.

Thanks again,
SB

 

[Chris11]

Uses Bezout's idenity. We have that we can write [math]a^{n-1}=kn+1[/math] Now, we have that 1=-kn+a^{n-1}. As this is the least possible positive number, it follows that it's the least positive positive number writable as a linear combo of n and a (n>1 otherwise, it's trivial). Hence, gcd(n,a)=1.

 

[Deveno]

a more group-theoretical approach (assuming n ≥ 2):

suppose a^n-1 = 1 (mod n).

then [a] (the residue of a mod n)

is a unit of Z_n (with inverse [a^n-2]).

this means gcd([a],n) = 1.

since a = [a] + kn, we have:

s([a]) + tn = 1 so:

s(a - kn) + tn = 1, and:

sa + (t-k)n = 1, which shows gcd(a,n) = 1.

 

[melese]

If $a\equiv b\pmod n$, then $(a,n)=(b,n)$. This can be seen by writing $a=b+nk$, for some integer $k$.

Here, $(a^{n-1},n)=(1,n)=1$.