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

Euler Phi Calculator

Adblocker detected! Please consider reading this notice.

This website is made possible by displaying online advertisements to its visitors. Please consider supporting us by disabling your ad blocker.

Or add comnuan.com to your ad blocking whitelist.

×