PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] residue systems (Definition)

Definition. Let $ m$ be a positive integer. A complete residue system modulo $ m$ is a set $ \{a_0,\,a_1,\,\ldots,\,a_{m-1}\}$ of integers containing one and only one representant from every residue class modulo $ m$. Thus the numbers $ a_\nu$ may be ordered such that for all $ \nu = 0,\,1,\,\ldots,\,m\!-\!1$, they satisfy $ a_\nu \equiv \nu \pmod{m}$.

The least non-negative remainders modulo $ m$, i.e. the numbers

$\displaystyle 0,\,1,\,\ldots,\,m\!-\!1$
form a complete residue system modulo $ m$ (see long division). If $ m$ is odd, then also the absolutely least remainders
$\displaystyle -\frac{m\!-\!1}{2},\,-\frac{m\!-\!3}{2},\,\ldots,\, -2,\,-1,\,0,\,1,\,2,\,\ldots,\,\frac{m\!-\!3}{2},\,\frac{m\!-\!1}{2}$
offer a complete residue system modulo $ m$.

Theorem 1. If $ \gcd(a,\,m) = 1$ and $ b$ is an arbitrary integer, then the numbers

$\displaystyle 0a\!+\!b,\,1a\!+\!b,\,2a\!+\!b,\,\ldots,\,(m\!-\!1)a\!+\!b$
form a complete residue system modulo $ m$.

One may speak also of a reduced residue system modulo $ m$, which contains only one representant from each prime residue class modulo $ m$. Such a system consists of $ \varphi(m)$ integers, where $ \varphi$ means the Euler's totient function.

Remark. A set of integers forms a reduced residue system modulo $ m$ if and only if
$ 1^\circ$ it contains $ \varphi(m)$ numbers,
$ 2^\circ$ its numbers are coprime with $ m$,
$ 3^\circ$ its numbers are incongruent modulo $ m$.

Theorem 2. If $ \gcd(a,\,m) = 1$ and $ \{k_1,\,k_2,\,\ldots,\,k_{\varphi(m)}\}$ is a reduced residue system modulo $ m$, then also the numbers

$\displaystyle k_1a,\,k_2a,\,\ldots,\,k_{\varphi(a)}a$
form a reduced residue system modulo $ m$.

Bibliography

1
K. V¨AISÄLÄ: Lukuteorian ja korkeamman algebran alkeet. Otava, Helsinki (1950).



"residue systems" is owned by pahio.
(view preamble)

View style:

See Also: prime residue class, totative, ${\mathbb{Z}}_n$

Also defines:  complete residue system, reduced residue system, least non-negative remainders, absolutely least remainders

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: coprime, Euler's totient function, prime residue class, contains, odd, long division, numbers, residue class, integer, positive
There are 6 references to this entry.

This is version 8 of residue systems, born on 2007-04-19, modified 2008-01-30.
Object id is 9221, canonical name is ResidueSystems.
Accessed 2262 times total.

Classification:
AMS MSC: 11-00 (Number theory :: General reference works )
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)