Math 2.0

Number theory Definition

Reduced residue system

Builds on Residue classCoprime integers

Definition

Let nn be a positive integer. A reduced residue system modulo nn is a set RR of integers with these properties. Each element of RR is coprime to nn. No two distinct elements of RR are congruent modulo nn. Each integer coprime to nn is congruent modulo nn to some element of RR.

Remarks

Thus RR contains exactly one element of each residue class of integers coprime to nn. It has φ(n)\varphi(n) elements, where φ\varphi is Euler's totient function. For example, {1,5,7,11}\{1, 5, 7, 11\} is a reduced residue system modulo 1212. If RR is a reduced residue system modulo nn and gcd⁡(a,n)=1\gcd(a, n) = 1, then {ar:r∈R}\{ a r : r \in R \} is also a reduced residue system modulo nn. This fact gives a proof of Euler's theorem.

Reading path

To understand this page from the ground up, read these 6 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…definitionResidue class, definition, no evidence levelResidue classdefinitionCoprime integers, definition, no evidence levelCoprime integersdefinitionReduced residue system, definition, no evidence levelReduced residue systemdefinition
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. Residue class definition
  5. Coprime integers definition
  6. Reduced residue system definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Reduced_residue_system, lead section
About this page
Tag0J0QEN1DZR
URIm2://0J0QEN1DZR
Aliasesreduced-system-of-residues
Kinddefinition
WritingW1 stated
MSC11A07
DefinesReduced residue system
UsesResidue class, Coprime integers

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (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.