Euler’s Totient Function

In number theory, Euler’s totient function counts the positive integers up to a given integer that are coprime with .

There is a very interesting relationship to Fermat’s Little Theorem.


  • If is a prime number, then
    • should be pretty obviously since all other numbers all coprime to
  • ??? If is a prime number and , then
    • Because there are exactly numbers that are divisible by
  • If and are coprime, then
  • Divisor Sum Property (established by Gauss):