Math 2.0

Number theory Theorem

Multiplicativity of the totient function

Builds on Euler's totient functionCoprime integersChinese remainder theorem

Statement

Let mm and nn be positive integers that are coprime. Then φ(mn)=φ(m)φ(n)\varphi(m n) = \varphi(m) \varphi(n), where φ\varphi is Euler's totient function.

Remarks

The proof uses the Chinese remainder theorem. It gives a bijection between the residues modulo mnm n and the pairs of residues modulo mm and modulo nn. A residue is coprime to mnm n if and only if both parts are coprime to their moduli. The hypothesis is necessary: φ(4)=2\varphi(4) = 2, but φ(2)φ(2)=1\varphi(2) \varphi(2) = 1. So φ\varphi is a multiplicative function. For example, φ(36)=φ(4)φ(9)=2⋅6=12\varphi(36) = \varphi(4) \varphi(9) = 2 \cdot 6 = 12.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionGreatest common divisor, definition, no evidence levelGreatest common divis…definitionCoprime integers, definition, no evidence levelCoprime integersdefinitionChinese remainder theorem, statement, no evidence levelChinese remainder the…statementEuler's totient function, definition, no evidence levelEuler's totient funct…definitionMultiplicativity of the totient function, statement, no evidence levelMultiplicativity of t…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Congruence modulo n definition
  3. Greatest common divisor definition
  4. Coprime integers definition
  5. Chinese remainder theorem statement
  6. Euler's totient function definition
  7. Multiplicativity of the totient function statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Euler%27s_totient_function, Phi is a multiplicative function
About this page
Tag0FSJA9M43W
URIm2://0FSJA9M43W
Kindstatement, theorem
WritingW0 stub
MSC11A25
StatusThis copy of the site has no build data. Run m2 status 0FSJA9M43W.
UsesEuler's totient function, Coprime integers, Chinese remainder theorem

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.