Log in

No account? Create an account

Previous Entry | Next Entry

Euler phi

In number theory there is Euler's φ(n) (or totient function), henceforth phi(n) because easier to type, which gives the number of numbers (sorry) less than n which are relatively prime to n. So for n=6, phi(n)=2, because only 1 and 5 are relatively prime to 6, {2 3 4} all sharing a divisor. Confusingly, 1 is both a divisor of 6 and considered relatively prime to it, with a g.c.d(1,6)=1.

The formula for phi is elegant: if n=p^a*q^b*r^c... p, q, r being distinct prime factors, then phi(n) = n * (1 - 1/p) * (1 - 1/q) * (1 - 1/r)...
So for n=6, 6*(1/2)*(2/3)=2
n=12, 12*(1/2)*(2/3)=4, {1 5 7 11}

Davenport (The Higher Arithmetic) gives a proof based on the Chinese remainder theorem, which I think I understood but have forgotten. Andrews (Number Theory) gives a different proof based on Moebius numbers, which has so far resisted my casual and sleep-deprived browsing.

But looked at another way, it seems obvious! That way is the Sieve of Eratosthenes, one of the few episodes I distinctly remember from elementary school math. The formula represents striking out all the multiples of p (including p), then striking from what is left all the multiples of q, and so on. All remaining numbers (including 1, heh) will share no prime factors with n.

So for n=6:
{1 2 3 4 5 6}
{1 3 5} 1/2 numbers remaining
{1 5} 2/3 of those remaining

That doesn't feel like a traditionally rigorous proof, but it also seems pretty straightforward and without obvious holes.

(If you multiply out the terms, you get something you can see as subtracting from the count the multiples of p, q, etc., then adding back in for the multiples of pq, pr, qr, etc. that were subtracted multiple times, and so on, but that seems less obviously correct than the first approach.)

See the comment count unavailable DW comments at http://mindstalk.dreamwidth.org/446114.html#comments



Damien Sullivan

Latest Month

August 2017


Powered by LiveJournal.com
Designed by Lilia Ahner