Difference between revisions of "Euler's Totient Theorem"
Borealbear (talk | contribs) |
Borealbear (talk | contribs) (→Introductory) |
||
Line 16: | Line 16: | ||
===Introductory=== | ===Introductory=== | ||
− | *(BorealBear) Find the last two digits of <math> 5^{81}-3^{81} </math>. | + | *(BorealBear) Find the last two digits of <math> 5^{81}-3^{81} </math>. [[Euler's Totient Theorem Problem 1 Solution|Solution]] |
− | *(BorealBear) Find the last two digits of <math> 3^{3^{3^{3}}} </math>. | + | *(BorealBear) Find the last two digits of <math> 3^{3^{3^{3}}} </math>. [[Euler's Totient Theorem Problem 2 Solution|Solution]] |
*([[2018 AMC 10B Problems/Problem 16|2018 AMC 10B]]) Let <math>a_1,a_2,\dots,a_{2018}</math> be a strictly increasing sequence of positive integers such that <cmath>a_1+a_2+\cdots+a_{2018}=2018^{2018}.</cmath> | *([[2018 AMC 10B Problems/Problem 16|2018 AMC 10B]]) Let <math>a_1,a_2,\dots,a_{2018}</math> be a strictly increasing sequence of positive integers such that <cmath>a_1+a_2+\cdots+a_{2018}=2018^{2018}.</cmath> | ||
What is the remainder when <math>a_1^3+a_2^3+\cdots+a_{2018}^3</math> is divided by <math>6</math>? | What is the remainder when <math>a_1^3+a_2^3+\cdots+a_{2018}^3</math> is divided by <math>6</math>? | ||
Line 23: | Line 23: | ||
<cmath>\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4</cmath> | <cmath>\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4</cmath> | ||
*([[1983 AIME Problems/Problem 6|1983 AIME]]) Let <math>a_n=6^{n}+8^{n}</math>. Determine the remainder upon dividing <math>a_ {83}</math> by <math>49</math>. | *([[1983 AIME Problems/Problem 6|1983 AIME]]) Let <math>a_n=6^{n}+8^{n}</math>. Determine the remainder upon dividing <math>a_ {83}</math> by <math>49</math>. | ||
− | |||
== See also == | == See also == |
Revision as of 13:17, 23 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
. 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
.