# can u solve this... Residue Classes

• Aug 15th 2006, 10:48 PM
earlkaize
can u solve this... Residue Classes
can you help me prove this one

Given m > 0. there are exactly m distinct residue classes modulo m, namely,
[0],[1],[2],...,[m-1]. :)

God bless you!
• Aug 16th 2006, 08:26 AM
ThePerfectHacker
Quote:

Originally Posted by earlkaize
Given m > 0. there are exactly m distinct residue classes modulo m, namely,
[0],[1],[2],...,[m-1]. :)

Not sure exactly what you mean. But I try anyway.

Consider the integral domain, \$\displaystyle \mathbb{Z}\$, regocnize that it is a commutative ring with unity (by definition) therefore you can speak of ideals. Note that for any \$\displaystyle m>0\$, that the coset \$\displaystyle m\mathbb{Z}\$ is an ideal in \$\displaystyle \mathbb{Z}\$. Form a factor ring, \$\displaystyle \mathbb{Z}/m\mathbb{Z}\$. And you end with,
\$\displaystyle \mathbb{Z}=\{...,-2m,-m,0,m,2m,...\}\$
\$\displaystyle 1+\mathbb{Z}=\{....,-2m+1,-m,1,m+1,2m+1,...\}\$
\$\displaystyle 2+\mathbb{Z}=\{...,-2m+2,-m+2,2,m+2,2m+2,...\}\$,
....
\$\displaystyle (m-1)+\mathbb{Z}=\{...-2m-1,-m-1,-1,m-1,2m-1,...\}\$
Note, all the intergers are divided among these cosets. Further, since cosets are equivalence classes they are all disjoint! Proof complete.
---
The ring formed by these cosets behaves just like the number under addition modulo \$\displaystyle m\$, in fact, it is a famous result that you should memorize that,
\$\displaystyle \boxed{\mathbb{Z}/m\mathbb{Z}\cong \mathbb{Z}_m}\$
• Aug 16th 2006, 03:09 PM
Rebesques
Well, consider an integer m. Euclidean division grants us that, for all integers n, there are only m cases for the residue when n is divided by m:

n=km, or n=km+1, or n=km+2,..., or n=km+m-1.

The numbers n included in every case form the residue classes, m in total.

This is the core of the idea, as PH explained (though his tough algebra eludes us!)