Modular arithmetic: Difference between revisions

Revision as of 19:27, 16 March 2025

Revision as of 19:30, 16 March 2025

Line 148:

The notation <math>\mathbb{Z}/m\mathbb{Z}</math> is used because this ring is the [[quotient ring]] of <math>\mathbb{Z}</math> by the [[ideal (ring theory)|ideal]] <math>m\mathbb{Z}</math>, the set formed by all {{math|''k m''}} with <math>k\in\mathbb{Z}.</math>

Considered as a [[group (mathematics)|group]] underUnder addition, <math>\mathbb Z/m\Z</math> is a [[cyclic group]], and all cyclic groups are isomorphic with <math>\mathbb Z/m\mathbb Z</math> for some {{mvar|m}}.<ref>Sengadir T., {{Google books|id=nglisrt9IewC|page=293|text=Zn is generated by 1|title=Discrete Mathematics and Combinatorics}}</ref>

The ring of integers modulo {{math|''m''}} is a [[field (mathematics)|field]], i.e., every nonzero element has a [[Modular multiplicative inverse|multiplicative inverse]], if and only if {{math|''m''}} is [[Prime number|prime]] (this ensures that every nonzero element has a [[Modular multiplicative inverse|multiplicative inverse]]). If {{math|1=''m'' = ''p''{{i sup|''k''}}}} is a [[prime power]] with {{math|''k'' > 1}}, there exists a unique (up to isomorphism) finite field <math>\mathrm{GF}(m) =\mathbb F_m</math> with {{math|''m''}} elements, which is ''not'' isomorphic to <math>\mathbb Z/m\mathbb Z</math>, which fails to be a field because it has [[zero-divisor]]s.

If {{math|''m'' > 1}}, <math>(\mathbb Z/m\mathbb Z)^\times</math> denotes the [[multiplicative group of integers modulo n|multiplicative group of the integers modulo {{math|''m''}}]] that are invertible. It consists of the congruence classes {{math|{{overline|''a''}}{{sub|''m''}}}}, where {{math|''a''}} [[coprime integers|is coprime]] to {{math|''m''}}; these are precisely the classes possessing a multiplicative inverse. They form an [[abelian group]] under multiplication; its order is {{math|''φ''(''m'')}}, where {{mvar|φ}} is [[Euler's totient function]]