Euler's totient function
Yeah, it has something to do with the greatest common divisor.
Thus, the two integersand are relatively prime if
Euler's totient function (denoted) counts the positive integers up to a given integer that are relatively prime to
Let's observewhen is a prime number. It holds:
That's because all integers smaller thanare relatively prime to the (prime) number
Let's now observe, where and are two distinct primes.
How many positive integers smaller thanare relatively prime to
The ones that are not relatively prime toare:
These arenumbers. Thus:
What ifwhere is prime? In this case, the integers that are not relatively prime to are:
And now to the general formula. Let's writeas where are distinct primes. Then:
Bob is still working on the proof of this formula though. But he has managed to greatly improve his (already magnificent) computational engine. Not only does it provide afunction, it also provides function now.
You can try the engine below, just type in something like: