Ivan Shishkin, Birch Grove

Euler’s totient function

Definition / Other /

English
EnglishFrançais

It is...

Practice this concept with exercises

1 / 2
  • We define Euler’s totient function as follows:
    ∀n∈N, φ(n)=∑k=1n1gcd(k,n)=1,\forall n \in \mathbb{N} ,\: \varphi (n)=\sum_{k=1}^{n}\mathbb{1}_{gcd(k,n)=1},meaning that φ(n)\varphi(n) equal the number of positive integer less (or equal) than n that are coprime with n.

    1. Show that ∀(a,b)∈N2, a∣b⇒φ(a)∣φ(b)\forall (a,b) \in \mathbb{N}^{2}, \: a|b \Rightarrow \varphi(a)| \varphi(b).

    2. Show that ∀(a,b)∈N2, gcd(a,b)=1⇒φ(a⋅b)=φ(a)⋅φ(b)\forall (a,b) \in \mathbb{N}^2, \: gcd(a,b) =1\Rightarrow\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b).

    3. Then deduce that,

    φ(n)=n⋅∏p∣np∈Pn(1−1p).\varphi(n)=n\cdot \prod_{\substack{p|n\\p\in \mathbb{P}}}^n \left(1-\frac{1}{p}\right).

    1. Moreover, show that n=∑d∣nφ(d)n =\sum_{d|n}\varphi(d).
Problems using this concept (2)
Problems using this concept (spoiler) (0)

No listed problems use this concept as a spoiler yet.