Welcome to our community

Be a part of something great, join today!

Number Theory The little theorem and its implication of coprimality.

bamuelsanks

New member
Apr 2, 2012
3
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

Well-known member
Feb 13, 2012
1,704
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

Active member
Jan 26, 2012
268
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.
 
Last edited:

chisigma

Well-known member
Feb 13, 2012
1,704
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

Active member
Jan 26, 2012
268
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.
 
Last edited:

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,708
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

Active member
Jan 26, 2012
268
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

New member
Apr 2, 2012
3
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

New member
Mar 20, 2012
3
Uses Bezout's idenity. We have that we can write \(\displaystyle a^{n-1}=kn+1\) 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

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
a more group-theoretical approach (assuming n ≥ 2):

suppose an-1 = 1 (mod n).

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

is a unit of Zn (with inverse [an-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

Member
Feb 24, 2012
27
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$.