Difference between revisions of "Euler's totient function"
Pianoman24 (talk | contribs) m (→Identities) |
m (Remove vandalism) |
||
(16 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
'''Euler's totient function''' <math>\phi(n)</math> applied to a [[positive integer]] <math>n</math> is defined to be the number of positive integers less than or equal to <math>n</math> that are [[relatively prime]] to <math>n</math>. <math>\phi(n)</math> is read "phi of n." | '''Euler's totient function''' <math>\phi(n)</math> applied to a [[positive integer]] <math>n</math> is defined to be the number of positive integers less than or equal to <math>n</math> that are [[relatively prime]] to <math>n</math>. <math>\phi(n)</math> is read "phi of n." | ||
− | == | + | == Formula == |
+ | |||
+ | Given the general [[prime factorization]] of <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}</math>, one can compute <math>\phi(n)</math> using the formula <cmath>\phi(n)= n\left(1-\frac{1}{p_1} \right) \left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_m}\right).</cmath> | ||
+ | |||
+ | |||
+ | == Derivation == | ||
To derive the formula, let us first define the [[prime factorization]] of <math> n </math> as <math> n =\prod_{i=1}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m} </math> where the <math>p_i </math> are distinct [[prime number]]s. Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to <math> n </math> that are relatively prime to it. | To derive the formula, let us first define the [[prime factorization]] of <math> n </math> as <math> n =\prod_{i=1}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m} </math> where the <math>p_i </math> are distinct [[prime number]]s. Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to <math> n </math> that are relatively prime to it. | ||
Line 24: | Line 29: | ||
<math>\phi(n)= n\left(1-\frac{1}{p_1} \right) \left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_m}\right).</math> | <math>\phi(n)= n\left(1-\frac{1}{p_1} \right) \left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_m}\right).</math> | ||
− | + | ||
+ | *Note: Another way to find the closed form for <math>\phi(n)</math> is to show that the function is multiplicative, and then breaking up <math>\phi(n)</math> into its prime factorization. | ||
== Identities == | == Identities == | ||
Line 34: | Line 40: | ||
(c) In fact, we also have for any <math>{a}, {b}</math> that <math>\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})</math>. | (c) In fact, we also have for any <math>{a}, {b}</math> that <math>\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})</math>. | ||
− | (d) If <math>p</math> is prime and <math>n\ge{1}</math> | + | (d) If <math>p</math> is prime and <math>n\ge{1},</math> then <math>\phi(p^n)=p^n-p^{n-1}</math> |
− | (e) For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>. | + | (e) For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors <math>d</math> of <math>n</math>. |
Proof. Split the set <math>\{1,2,\ldots,n\}</math> into disjoint sets <math>A_d</math> where for all <math>d\mid n</math> we have | Proof. Split the set <math>\{1,2,\ldots,n\}</math> into disjoint sets <math>A_d</math> where for all <math>d\mid n</math> we have | ||
Line 43: | Line 49: | ||
<cmath>A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.</cmath> | <cmath>A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.</cmath> | ||
Thus by the definition of Euler's phi we have that <math>|A_d^\prime|=\phi (n/d)</math>. As every integer <math>i</math> which satisfies <math>1\leq i\leq n</math> belongs in exactly one of the sets <math>A_d</math>, we have that | Thus by the definition of Euler's phi we have that <math>|A_d^\prime|=\phi (n/d)</math>. As every integer <math>i</math> which satisfies <math>1\leq i\leq n</math> belongs in exactly one of the sets <math>A_d</math>, we have that | ||
− | <cmath>n=\sum_{d \mid n}\ | + | <cmath>n=\sum_{d \mid n}\phi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).</cmath> |
+ | |||
+ | |||
+ | (f) Another interesting thing to note is that <math>\phi(n)\leq n - 1</math>. This does seem very obvious but is helpful in solving many problems. | ||
+ | |||
+ | ==Graph== | ||
+ | |||
+ | [[Image:Euler_totient_50000.png]] | ||
==Notation== | ==Notation== | ||
Sometimes, instead of <math>\phi</math>, <math>\varphi</math> is used. This variation of the Greek letter ''phi'' is common in textbooks, and is standard usage on the English [[Wikipedia]] | Sometimes, instead of <math>\phi</math>, <math>\varphi</math> is used. This variation of the Greek letter ''phi'' is common in textbooks, and is standard usage on the English [[Wikipedia]] | ||
+ | |||
+ | ==Video== | ||
+ | https://youtu.be/T7INnve59JM | ||
== See Also == | == See Also == | ||
Line 56: | Line 72: | ||
[[Category:Functions]] | [[Category:Functions]] | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
+ | |||
+ | {{stub}} |
Latest revision as of 21:07, 4 February 2025
Euler's totient function applied to a positive integer
is defined to be the number of positive integers less than or equal to
that are relatively prime to
.
is read "phi of n."
Contents
[hide]Formula
Given the general prime factorization of , one can compute
using the formula
Derivation
To derive the formula, let us first define the prime factorization of as
where the
are distinct prime numbers. Now, we can use a PIE argument to count the number of numbers less than or equal to
that are relatively prime to it.
First, let's count the complement of what we want (i.e. all the numbers less than or equal to that share a common factor with it). There are
positive integers less than or equal to
that are divisible by
. If we do the same for each
and add these up, we get
![\[\frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.\]](http://latex.artofproblemsolving.com/5/7/6/576821b22ebb5e1a9c986631792e516828e99b1c.png)
But we are obviously overcounting. We then subtract out those divisible by two of the . There are
such numbers. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is
![\[\sum_{1 \le i \le m}\frac{n}{p_i} - \sum_{1 \le i_1 < i_2 \le m}\frac{n}{p_{i_1}p_{i_2}} + \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}.\]](http://latex.artofproblemsolving.com/1/a/5/1a54da6486432515085420e1ba73b8010bf4351b.png)
This sum represents the number of numbers less than sharing a common factor with
, so
- Note: Another way to find the closed form for
is to show that the function is multiplicative, and then breaking up
into its prime factorization.
Identities
(a) For prime ,
, because all numbers less than
are relatively prime to it.
(b) For relatively prime ,
.
(c) In fact, we also have for any that
.
(d) If is prime and
then
(e) For any , we have
where the sum is taken over all divisors
of
.
Proof. Split the set into disjoint sets
where for all
we have
Now
if and only if
. Furthermore,
if and only if
. Now one can see that the number of elements of
equals the number of elements of
Thus by the definition of Euler's phi we have that
. As every integer
which satisfies
belongs in exactly one of the sets
, we have that
(f) Another interesting thing to note is that . This does seem very obvious but is helpful in solving many problems.
Graph
Notation
Sometimes, instead of ,
is used. This variation of the Greek letter phi is common in textbooks, and is standard usage on the English Wikipedia
Video
See Also
This article is a stub. Help us out by expanding it.