Math 2.0

Number theory Proposition

Order of the group of units of Z/nZ is Euler's totient

Builds on Units of Z/nZ are the residues coprime to nOrder of a group

Statement

Let n≥1n \geq 1 be an integer. Then the order of the group (ℤ/nℤ)×(\mathbb{Z}/n\mathbb{Z})^\times is φ(n)\varphi(n). Here φ(n)\varphi(n) is the number of integers aa with 0≤a≤n−10 \leq a \leq n - 1 and gcd⁡(a,n)=1\gcd(a, n) = 1.

Remarks

The proof is a count, because the units of Z/nZ are the residues coprime to n. For a prime pp, the order is φ(p)=p−1\varphi(p) = p - 1. For example, (ℤ/9ℤ)×={1,2,4,5,7,8}(\mathbb{Z}/9\mathbb{Z})^\times = \{1, 2, 4, 5, 7, 8\} has order φ(9)=6\varphi(9) = 6. With Lagrange's theorem, this gives Euler's theorem: aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n} for each aa coprime to nn.

Reading path

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

Show the path as a graph
Binary operation, definition, no evidence levelBinary operationdefinitionGroup, concept, no evidence levelGroupconceptGroup of units of Z/nZ, object, no evidence levelGroup of units of Z/nZobjectAssociativity, definition, no evidence levelAssociativitydefinitionIdentity element, definition, no evidence levelIdentity elementdefinitionOrder of a group, definition, no evidence levelOrder of a groupdefinitionSemigroup, definition, no evidence levelSemigroupdefinitionInverse element, definition, no evidence levelInverse elementdefinitionMonoid, definition, no evidence levelMonoiddefinitionGroup of units of a monoid, definition, no evidence levelGroup of units of a m…definitionUnits of Z/nZ are the residues coprime to n, statement, no evidence levelUnits of Z/nZ are the…statementOrder of the group of units of Z/nZ is Euler's totient, statement, no evidence levelOrder of the group of…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. Binary operation definition
  2. Group concept
  3. Group of units of Z/nZ object
  4. Associativity definition
  5. Identity element definition
  6. Order of a group definition
  7. Semigroup definition
  8. Inverse element definition
  9. Monoid definition
  10. Group of units of a monoid definition
  11. Units of Z/nZ are the residues coprime to n statement
  12. Order of the group of units of Z/nZ is Euler's totient statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n, Structure
  2. Web https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n, n = 9
About this page
Tag0S7495H4HM
URIm2://0S7495H4HM
Kindstatement, proposition
WritingW0 stub
MSC11A07, 11A25
StatusThis copy of the site has no build data. Run m2 status 0S7495H4HM.
UsesUnits of Z/nZ are the residues coprime to n, Order of a group

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

Used by