Difference between revisions of "Euler's Totient Theorem"
m (→Theorem) |
Megaboy6679 (talk | contribs) (→See also) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 11: | Line 11: | ||
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>\ | + | 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>\gcd(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)} \pmod{m} </math> <math> \implies </math> <math> a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)} \pmod{m} </math> <math> \implies </math> <math> a^{\phi (m)} \equiv 1 \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>. <math>\square</math> |
==Group Theoretic Proof== | ==Group Theoretic Proof== | ||
− | Define the set <math>(\mathbb{Z}/n\mathbb{Z})^{\times}=\{a\in\mathbb{N}\,|\,1\le a <n \wedge \gcd(a,n)=1\}</math>. Trivially we have that <math>|(\mathbb{Z}/n\mathbb{Z})^{\times}|=\varphi(n)</math>. From there, there exists a sufficient <math>k</math> such that <math>a^{k}\equiv 1\pmod{n}</math>, and by Lagrange's Theorem <math>bk|\varphi(n)</math> which means | + | Define the set <math>(\mathbb{Z}/n\mathbb{Z})^{\times}=\{a\in\mathbb{N}\,|\,1\le a <n \wedge \gcd(a,n)=1\}</math>. Trivially we have that <math>|(\mathbb{Z}/n\mathbb{Z})^{\times}|=\varphi(n)</math>. From there, there exists a sufficient <math>k</math> such that <math>a^{k}\equiv 1\pmod{n}</math>, and by [[Lagrange's Theorem]] <math>bk|\varphi(n)</math> which means |
− | <math>a^{\varphi(n)}\equiv a^{bk} \equiv (a^{k})^b\equiv 1^b\equiv 1\pmod{n} </math>, completing the proof <math>\square</math> | + | <math>a^{\varphi(n)}\equiv a^{bk} \equiv (a^{k})^b\equiv 1^b\equiv 1\pmod{n} </math>, completing the proof. <math>\square</math> |
==Problems== | ==Problems== | ||
Line 32: | Line 32: | ||
* [[Number theory]] | * [[Number theory]] | ||
* [[Modular arithmetic]] | * [[Modular arithmetic]] | ||
+ | * [[Lagrange's Theorem]] | ||
* [[Euler's totient function]] | * [[Euler's totient function]] | ||
* [[Carmichael function]] | * [[Carmichael function]] |
Latest revision as of 17:45, 21 March 2023
Euler's Totient Theorem is a theorem closely related to his totient function.
Contents
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.
Direct 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
.
Group Theoretic Proof
Define the set . Trivially we have that
. From there, there exists a sufficient
such that
, and by Lagrange's Theorem
which means
, completing the proof.
Problems
Introductory
- (BorealBear) Find the last two digits of
. (Solution)
- (BorealBear) Find the last two digits of
. (Solution)
- (2018 AMC 10B) Let
be a strictly increasing sequence of positive integers such that
What is the remainder when is divided by
?
- (1983 AIME) Let
. Determine the remainder upon dividing
by
.