Euler's Totient Function

Definition

Euler’s totient function is defined as

---

Properties

Theorem is Multiplicative Function

Proof: Consider . Then consider the set numbers . By Euclid’s Division Lemma every such number can be written in the form with . You can think of putting this in a grid with each being in row index and column index .

Let be the subset of that has coefficient for e.g. . Each forms a complete residue class as so for each there are elements coprime to . Then let be the subset of with remainder e.g. . Each forms a complete residue class as so for each there are elements coprime to .

So the total amount that is coprime to is - You can think this as starting in the top row there are elements that are coprime to and each of them form a column in which there are that are also coprime to . Only the columns where the first element is coprime to work as any element that has a common factor with will form a column in which all those elements share that common factor with . (This is due to the fact that )

Theorem Proof: Every number other than a multiple of is coprime to . There are multiples of and there are numbers so combing them we get .

Theorem Let . Proof: Using the previous theorem, Since is multiplicative and primes are pairwise coprime.

Theorem

Proof: Let . Every positive divisor

Using the fact that is multiplicate we get . You can repeatedly factor out from the summation with as it is constant as you are changing all up to but not including so the summation is constant and can be factored out. This obtains

For each term we get which using gets a telescoping sum of . Replacing every sum we get .

Theorem Proof: INSERT PROOF