# 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.

Mentioned in ?
References in periodicals archive ?
Therefore [a.sub.1] + b, [a.sub.2] + b, ..., [a.sub.[phi](m)] + b is also a reduced residue system modulo m.
is not a reduced residue system modulo m which is a contradiction.
Suppose that [a.sub.1], [a.sub.2], ..., [a.sub.[phi](m)] is a reduced residue system modulo m and (k,m) = 1, then k[a.sub.1] + b, k[a.sub.2] +b, ..., k[a.sub.[phi](m)] +b is also a reduced residue system modulo m if and only if [p.sub.1] ...
Since (k,m) = 1, k[a.sub.1], k[a.sub.2], ..., k[a.sub.[phi](m)] is a reduced residue system modulo m.
Suppose that [a.sub.1], [a.sub.2], ..., [a.sub.[phi](m)] is a reduced residue system modulo m and (k,m) > 1, then k[a.sub.1] + b, k[a.sub.2] +b, ..., k[a.sub.[phi](m)] +b is also a reduced residue system modulo m if and only if all the following conditions hold: (k,m) = 2, m = 4t + 2 (t = 0, 1, 2, ...), 2 [??] b and [p.sub.2] ...
Since k[a.sub.1]+ b, k[a.sub.2]+b, ..., k[a.sub.[phi](m)]+b is a reduced residue system modulo m, we have k[a.sub.i] +b [not equivalent to] k[a.sub.j] +b (mod m) for 1 [less than or equal to] i < j [less than or equal to] [phi](m).
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).

Site: Follow: Share:
Open / Close