As I understand Euler's Generalization of Fermat's little theorem in Modulo Arithmetic, it is:
$a^{\phi(n)} \equiv 1 \pmod{n}$
However, I have also seen a version of the theorem which seems more understandable and goes:
"If b and n have a highest common factor of 1, then $b^x \equiv 1 \pmod{n}$, for some number x less than n".
-
Are these the same? Are both valid? And If the second is valid, then why, for example, is $5^3 \equiv 1 \pmod{8}$ not true? As I see it, 5 and 8 are relatively prime, and 3 is smaller than 8, so why doesn't this work?
-
And just to clarify: If the 2nd isn't true, phi in the first is simply any real number? So, for example, if $2^6 \equiv 1 \pmod{9}$ (true), then the phi is 2/3?
-
Linked to the 3rd, could someone please give me a general explanation of the theorem?
- Application of the theorem: How would I evaluate the following using Euler's theorem?
a) $3^{101} \mod 16$.
b) $5^6 \mod{14}$.
Thanks!
Best Answer
The exact formulation of Euler's theorem is $$\gcd(a,n)=1\implies a^{\varphi(n)}\equiv 1\mod n$$ where $\varphi(n)$ denotes the totient function.
Since $\varphi(n)\le n-1<n$, the alternative formulation is valid and basically the same. The smallest positive integer $\ k\ $ with $\ a^k\equiv 1\mod n\ $ must be a divisor of $\ \varphi(n)\ $. The exponent is however not arbitary. "for some" means that there exists one, not that it holds for every exponent.
A further improvement of Euler's theorem can be achieved with the Carmichael function.