Congruent Classes

Def Congruent Modulo We say that two integers and are congruent modulo if they give the same residue upon devision by . All the following are equivalent:

Prop Congruent modulo is an equivalence relation.

Def Congruent Class The congruent class of an integer modulo an integer is the set of all integers such that : Prop Congruent class is an equivalence class.

Def Define the group of -congruent class with :

Prop is a cyclic group.

Def Let . Define with

Prop is a group. Proof For all , we have

And exists as an identity as . Since there exist integers such that which by taking residue modulo gives e.g.

Prop

Def Multiplicative Order Let be an integer number coprime to a prime number . The multiplicative order of modulo or is the least positive integer such that . The multiplicative order is equivalent to the order of in group .

Def Euler -Function Let . Euler function is defined to be: