Difference between revisions of "Euler's Totient Theorem"
m (→Proof) |
Borealbear (talk | contribs) |
||
| Line 12: | Line 12: | ||
Consider the set of numbers <math>A = \{ n_1, n_2, ... n_{\phi(m)} \} \pmod{m}</math> such that the elements of the [[set]] are the numbers relatively [[prime]] to <math>m</math>. | Consider the set of numbers <math>A = \{ n_1, n_2, ... n_{\phi(m)} \} \pmod{m}</math> such that the elements of the [[set]] are the numbers relatively [[prime]] to <math>m</math>. | ||
It will now be proved that this set is the same as the set <math>B = \{ an_1, an_2, ... an_{\phi(m)} \} \pmod{m}</math> where <math> (a, m) = 1</math>. All elements of <math>B</math> are relatively prime to <math>m</math> so if all elements of <math>B</math> are distinct, then <math>B</math> has the same elements as <math>A.</math> In other words, each element of <math>B</math> is congruent to one of <math>A</math>.This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math><math>\pmod{m}</math> → <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math><math>\pmod{m}</math> → <math>a^{\phi (m)} \equiv 1</math><math>\pmod{m}</math> as desired. Note that dividing by <math> n_1 n_2 ... n_{\phi(m)}</math> is allowed since it is relatively prime to <math>m</math>. | It will now be proved that this set is the same as the set <math>B = \{ an_1, an_2, ... an_{\phi(m)} \} \pmod{m}</math> where <math> (a, m) = 1</math>. All elements of <math>B</math> are relatively prime to <math>m</math> so if all elements of <math>B</math> are distinct, then <math>B</math> has the same elements as <math>A.</math> In other words, each element of <math>B</math> is congruent to one of <math>A</math>.This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math><math>\pmod{m}</math> → <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math><math>\pmod{m}</math> → <math>a^{\phi (m)} \equiv 1</math><math>\pmod{m}</math> as desired. Note that dividing by <math> n_1 n_2 ... n_{\phi(m)}</math> is allowed since it is relatively prime to <math>m</math>. | ||
| + | |||
| + | ==Problems== | ||
| + | |||
| + | ===Introductory=== | ||
| + | *(BorealBear) Find the last two digits of <math> 5^81-3^81 </math>. | ||
| + | *(BorealBear) Find the last two digits of <math> 3^{3^{3^{3}}} </math>. | ||
== See also == | == See also == | ||
Revision as of 15:06, 22 April 2021
Euler's Totient Theorem is a theorem closely related to his totient function.
Theorem
Let 
be Euler's totient function. If 
is a positive integer, 
is the number of integers in the range 
which are relatively prime to . If 
is an integer and 
is a positive integer relatively prime to 
,Then 
.
Credit
This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies it when 
is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.
Proof
Consider the set of numbers 
such that the elements of the set are the numbers relatively prime to .
It will now be proved that this set is the same as the set 
where 
. All elements of 
are relatively prime to so if all elements of are distinct, then has the same elements as 
In other words, each element of is congruent to one of 
.This means that 
→ 
→ 
as desired. Note that dividing by 
is allowed since it is relatively prime to .
Problems
Introductory
- (BorealBear) Find the last two digits of
. - (BorealBear) Find the last two digits of
.
.
.
