Reduced Residue System


Also found in: Acronyms, Wikipedia.

Reduced Residue System

 

the part of a complete residue system that consists of numbers relatively prime to the modulus m. A reduced residue system contains Φ(m) numbers [Φ(m) is the number of integers relatively prime to m and less than m]. Every set of Φ(m) integers that is not congruent modulo m and that is relatively prime to m forms a reduced residue system modulo m.

References in periodicals archive ?
If we replace the complete system of incongruent residues modulo m in this theorem by a reduced residue system modulo m, the result is not true.
phi](m)] is a reduced residue system modulo m, then k[a.
Let n; d be positive integers, n > 1 and d|n: Then every reduced residue system modulo n can be divided into [phi](n)/[phi](d) reduced residue systems modulo d.
phi](m)] + b is also a reduced residue system modulo m.
is not a reduced residue system modulo m which is a contradiction.
phi](m)]+b is a reduced residue system modulo m, we have k[a.
The number of distinct integers in a reduced residue system (mod n) is important here.
Note that a reduced residue system (mod n) is a complete system of nonzero residues (mod n) if and only if n is prime.
Thus there exist p - 1 distinct numbers (mod p) all coprime with p - that is, a reduced residue system with p - 1 distinct numbers (mod p) - hence p is prime.
Thus there exist p - 1 distinct numbers (mod p) all coprime with p, that is, a reduced residue system with p - 1 distinct numbers (mod p).

Full browser ?