Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Euler's phi function

Revision as of 14:33, 18 June 2006 by Chess64 (talk | contribs) (→‎Formulas: \left(and\right))

Euler's phi function determines the number of integers less than a given positive integer that are relatively prime to that integer.

Formulas

Given the prime factorization of ${n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}$, then one formula for $\phi(n)$ is $\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_n}\right)$.

See also

Identities

For prime p, $\phi(p)=p-1$, because all numbers less than ${p}$ are relatively prime to it.

For relatively prime ${a}, {b}$, $\phi{(a)}\phi{(b)} = \phi{(ab)}$.

Other Names

  • Totient Function
  • Euler's Totient Function
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_phi_function&oldid=2729"