## 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}$.