Explain and Apply Euler's Generalisation of Fermat's Theorem

Question

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

1. 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?

2. 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?

3. Linked to the 3rd, could someone please give me a general explanation of the theorem?

4. 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!

Answer 1

@AnuragA and @Peter have set you on the right track. Here is further thorough clarification.

1. Both are correct, but the first is more common because the 2nd one is slightly more misleading. It says for some number , this doesn't mean for every number < you will have the result. That is why your example is not true, as you pointed out.

2. () refers to the totient function - essentially, refers to the number of natural numbers smaller than n, which are relatively prime (i.e HCF is 1) to $n$. For example, (8) is 4 (1, 3, 5, 7).

3. Essentially, for some number b which is relatively prime to the modulo given, n, b to the totient function of n is congruent to 1 modulo n. It generalises Fermat's little theorem to non-primes.

4. (a) (16)= 8, so $3^8 \cong 1$ mod 16. Since $3^{101}$ = $(3^8)^{12} * 3^5$, we can say that this is equal to $1 * 3^5 $mod 16. So since $3^5$ = 243, and $243 \cong 3$ mod 16, we can now say that $3^{101} \cong 3$ mod 16.

   (b) this is slightly more challenging - I encourage you to try and work it out equipped with this knowledge...

Answer 2

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.

Answer 3

1. Both statements are valid, but they're not exactly the same. As you've stated it, the second is trivial, because $\ b^0\equiv1\pmod{n}\ $, and $\ 0<n\ $. Even if you make it non-trivial by requiring $\ n\ $ to be positive, it's still not quite the same. It merely tells you that $\ b^x\equiv 1\pmod{n}\ $ for some $\ x\in \{1,2,\dots,n-1\}\ $, whereas the first gives you a specific value of $\ x\ $, namely $\ \varphi(n)\ $, that does the job.
2. The second statement doesn't say that $\ b^x\equiv 1\pmod{n}\ $ for any $\ x\ $ in the required range, merely that it's true for some such $\ x\ $. When $\ n=8\ $ and $\ b=5\ $, then there are three values of $\ x\ $ in the set $\ \{1,2,3,4,5,6,7\}$ for which $\ 5^x\equiv1\pmod{8}\ $, including $\ \varphi(8)=4\ $, but $\ x=3\ $ isn't one of them.
3. (Part of which has now disappeared from the question) No. If $\ n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}\ $, where $\ p_1,p_2,\dots,p_r\ $ are prime numbers, then $\ \varphi(n)\ $ is the specific number $$(p_1-1)(p_2-1)\dots(p_r-1) p_1^{a_1-1}p_2^{a_2-1}\dots p_r^{a_r-1}\ . $$ So $\ \varphi(9)= \varphi(3^2) =(3-1)\cdot3^{2-1}=6\ $, for instance, and $\ \varphi(8)= \varphi(2^3) =(2-1)\cdot2^{3-1}=4\ $.

3b. You'll find a proof of Euler's theorem in its Wikipedia article.}

4.\begin{align}\ \varphi(16)&=\varphi{2^4}=(2-1)\cdot2^3=8\\ \therefore\ \ 3^{101}&=3^{8\cdot12}3^5\\ &\equiv1\cdot3^5\pmod{16}\\ &\equiv 3^4\cdot3\pmod{16}\\ &\equiv 3 \pmod{16} \end{align} 5. \begin{align}\ \varphi(14)&=\varphi(2\cdot7)=(2-1)(7-1)=6\\ \therefore\ \ 5^6&\equiv 1 \pmod{14} \end{align}

Answer 4

In response to @global05's wonderful answer, my attempt at 4. (b):

(14) = 6 (1, 3, 5, 9, 11, 13).

So $5^{6*14} \cong 1$ mod 14. so $(5^6)^{14} \cong 1$ mod 14.

But the 14th root of 1 is 1. So $5^6$ must be $=1$.