![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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.)
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.)