Ivan Shishkin, Birch Grove

Euler’s totient function

Definition / Other / Stub

English
EnglishFrançais
This article is a stub
Stub. This concept is still a minimal draft.

It is...

Practice this concept with exercises

1 / 2
  • We define Euler’s totient function as follows:
    nN,φ(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,abφ(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φ(ab)=φ(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)=npnpPn(11p).\varphi(n)=n\cdot \prod_{\substack{p|n\\p\in \mathbb{P}}}^n \left(1-\frac{1}{p}\right).

    1. Moreover, show that n=dnφ(d)n =\sum_{d|n}\varphi(d).
    Open exerciseDifficulty 29/100 · 0 solutions · 0 hints
Problems using this concept (1)
Problems using this concept (spoiler) (0)

No listed problems use this concept as a spoiler yet.