Euler Totient Calculator
Euler's totient function or Euler's phi function, $\phi(n)$, of a positive integer $n$ is a function that counts the positive integers less than or equal to $n$ that are relatively prime to $n$, i.e. their gcd is equal to 1. This calculator find $\phi(n)$ using Euler's product formula: \[ \phi(n) = n \prod_{p|n}\left(1-\frac{1}{p}\right) \] where the product is over the distinct prime factors of $n$. Euler's phi function is used in Euler's theorem which state that if $a$ and $n$ are relatively prime then \[ a^{\phi(n)}\equiv 1\mod{n} \] This is an example showing how to use Euler's theorem and $\phi(n)$ to find the remainders of dividing $7^{100}$ with $10$ and $11$. The remainers are calculated from $7^{100}\mod{10}$ and $7^{100}\mod{1}$, respectively. As $7$ and $10$ are relatively prime and $\phi(10)=4$ we get (using Euler's theorem) \[ 7^4\equiv 1\mod{10} \] Raising to the power of $25$ we get $7^{100}=(7^4)^{25}\equiv 1^{25}\equiv 1\mod{10}$, obtaining the remainder of $1$. Similarly for $\phi(11)=10$ we get $7^{10}\equiv 1\mod{11}$ so $7^{100}\equiv 1\mod{11}$.