Ivan Shishkin, Rye (1878)

Problems/Number theoryExerciseUnreviewed

On Euler’s totient function

by Cypress·
29
Difficulty scaleÉchelle de difficulté

This score reflects both the level of the required concepts and the difficulty of the solution.Ce score tient compte à la fois du niveau des notions nécessaires et de la difficulté de la résolution.

  1. 110First steps / middle schoolPremiers pas / collège
  2. 1125Beginner / high schoolDébutant / lycée
  3. 2650Intermediate / undergraduateIntermédiaire / licence
  4. 5170Advanced / graduateAvancé / master
  5. 7190Expert / specializedExpert / spécialisé
  6. 91100Research levelNiveau recherche
These levels are approximate guides.Ces niveaux sont des repères approximatifs.
·
English
EnglishFrançais
This translation may be outdated. Its source text has changed since revision 1851.
Unreviewed. This problem has not been reviewed by trusted users yet.

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).
I solved itMark it doneAdd to my listKeep it in your list

Solutions

0
Report

For an unclear, ambiguous, or possibly incorrect statement, please use the Discussion tab on the right. Report content that needs moderator intervention, such as dangerous, clearly non-mathematical, or plagiarized content.