Difference between revisions of "Euler's Totient Theorem"
(Added a proof of the theorem using Group Theory.) |
m (→Theorem) |
||
Line 2: | Line 2: | ||
== Theorem == | == Theorem == | ||
− | Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>n</math> is a positive integer, <math>\phi{(n)}</math> is the number of integers in the range <math>\{1,2,3\cdots{,n}\}</math> which are relatively prime to <math>n</math>. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>, | + | Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>n</math> is a positive integer, <math>\phi{(n)}</math> is the number of integers in the range <math>\{1,2,3\cdots{,n}\}</math> which are relatively prime to <math>n</math>. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>, then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>. |
== Credit == | == Credit == |
Revision as of 21:21, 16 March 2023
Euler's Totient Theorem is a theorem closely related to his totient function.
Contents
[hide]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 .