Algebra: Section - 2 (Rings) | Mathematics Optional Notes for UPSC PDF Download

 Page 1


Edurev123 
SECTION - II 
RINGS 
5. RINGS AND IDEALS 
In groups, we had a set and an algebraic structure with ONE binary composition defined 
on it. Now we consider algebraic structures with two binary compositions: 1
°
 Addition, 
and 2
°
 Multiplication denoted respectively by + and . 
Let ?? be a non-ernpty set, such that, given any two elements ?? and ?? in ?? there 
corresponds in R a  well-defined element a+b called their sum, and a well-defined 
element a.b, called their product. 
1
°
?? ×?? ???         2
°
?? ×?? ??? 
(?? ,?? )??? +??        (?? ,?? )??? .?? 
        Addition                   Multiplication 
We call R a ring if the following, laws hold for arbitrary elements a, b, c, …. of ?? . 
(5.1) (A.1) ?? +?? =?? +?? (Commutative law for Addition)  
         (?? .2)?? +(?? +?? )=(?? +?? )+?? ( Associative law for Addition) 
          (A.3) For any two elements ?? ,?? ;3 always ?? satisiying the equation. 
?? +?? =?? 
(Inverse Law for addition) 
(M) a (bc) = (ab) c (Associative law for multiplication) 
(D) The two binary compositions are interrelated by the Distributive Law. 
?? (?? +?? )=???? +???? and (?? +?? )?? =???? +???? 
If we ignore the binary composition: multiplication in R, the laws (A.1), (A.2) and (A.3) 
assert that (?? ,+) is a commutative group. whose neutral element will be denoted by 0. 
0=?? -?? for all ?? ,?? +0=?? for all ?? 
(?? ,+) is called the underlying additive group of the ring. If, in addition to the laws (5.1), 
one has (5.2) (c) ???? = ba (Commutative law for multiplication). also, we say that ?? is a 
commutative ring. 
Page 2


Edurev123 
SECTION - II 
RINGS 
5. RINGS AND IDEALS 
In groups, we had a set and an algebraic structure with ONE binary composition defined 
on it. Now we consider algebraic structures with two binary compositions: 1
°
 Addition, 
and 2
°
 Multiplication denoted respectively by + and . 
Let ?? be a non-ernpty set, such that, given any two elements ?? and ?? in ?? there 
corresponds in R a  well-defined element a+b called their sum, and a well-defined 
element a.b, called their product. 
1
°
?? ×?? ???         2
°
?? ×?? ??? 
(?? ,?? )??? +??        (?? ,?? )??? .?? 
        Addition                   Multiplication 
We call R a ring if the following, laws hold for arbitrary elements a, b, c, …. of ?? . 
(5.1) (A.1) ?? +?? =?? +?? (Commutative law for Addition)  
         (?? .2)?? +(?? +?? )=(?? +?? )+?? ( Associative law for Addition) 
          (A.3) For any two elements ?? ,?? ;3 always ?? satisiying the equation. 
?? +?? =?? 
(Inverse Law for addition) 
(M) a (bc) = (ab) c (Associative law for multiplication) 
(D) The two binary compositions are interrelated by the Distributive Law. 
?? (?? +?? )=???? +???? and (?? +?? )?? =???? +???? 
If we ignore the binary composition: multiplication in R, the laws (A.1), (A.2) and (A.3) 
assert that (?? ,+) is a commutative group. whose neutral element will be denoted by 0. 
0=?? -?? for all ?? ,?? +0=?? for all ?? 
(?? ,+) is called the underlying additive group of the ring. If, in addition to the laws (5.1), 
one has (5.2) (c) ???? = ba (Commutative law for multiplication). also, we say that ?? is a 
commutative ring. 
In a commutative ring either of the distributive laws is a consequence of the other. 
since we have studied, in detail, algebraic, structures with one binary composition, 
Groups, we can apply the results of Section to the additive group (?? 1
+?) of the ring. 
In particular, ?  precisely one element: 0 with the property   ?? +0=?? ?????? ?????? ?? ???? ?? 
(the null element or zero element of R) There exists precisely  one element -a such that 
?? +?? = ?? +(-?? )=0 for all ?? . 
Instead of ?? +(-?? ) we simply write ?? -?? . For a natural number =1,2 ,3… we put ?? .?? =
?? +?? +?+?? (?? terms) 
For a negative integer ?? ,=-1,-2,-3, ... we put ?? '
?? =(-?? ):?? =??¨·(-?? )=(-?? )+
?-?? )
'
.. .+(-?? ) (n terms)  
For the number 0 ; we put, for any ?? in ?? 
0.?? =0 (the zero-element of ?? ) 
The zero on the left side is a number whereas the zero on the right side is the null 
element of R : 
Then, if we put ?? = the set of all integers ={(0,±1,±2,…,±?? ;…} 
We have, for all ?? ,?? in ?? and ?? ,?? in ?? . 
(5.3) (?? +?? )?? =?? .?? +?? ·?? ,?? .(?? .?? )=(?? ?? )?? ,       ?? (?? +?? )=???? +???? 
It is easy to verify that 
a. (-?? )=-(???? );(-?? )·?? =-(???? );(-?? )(-?? )=?? .?? 
?? (?? -?? )=???? -???? ,(?? -?? )?? =???? -???? 
?? (?? 1
+?+?? ?? )=?? ?? 1
+?+?? ?? 1
 
(?? 1
+..+?? ?? )?? =?? 1
?? +?+?? ?? ?? 
 
(5.4) ?? ?? ·?? ?? =?? ?? ,?? =?? ?? ·?? ?? ,(?? ?? ,?? )
?? =?? ?? ,?? ?? (5.5) If ?? is a commutative ring, i.e., ab 
=ba for all ?? ,?? in ?? , then (???? )
?? =?? ?? ?? ?? ?? 
 
Example 
The set of complex numbers a + ib. 
?? ??? ,?? ??? forms a commutative ring, called the ring of Gaussian integers. 
[5:1] The ring of residue classes mod.m:Z(m) 
Page 3


Edurev123 
SECTION - II 
RINGS 
5. RINGS AND IDEALS 
In groups, we had a set and an algebraic structure with ONE binary composition defined 
on it. Now we consider algebraic structures with two binary compositions: 1
°
 Addition, 
and 2
°
 Multiplication denoted respectively by + and . 
Let ?? be a non-ernpty set, such that, given any two elements ?? and ?? in ?? there 
corresponds in R a  well-defined element a+b called their sum, and a well-defined 
element a.b, called their product. 
1
°
?? ×?? ???         2
°
?? ×?? ??? 
(?? ,?? )??? +??        (?? ,?? )??? .?? 
        Addition                   Multiplication 
We call R a ring if the following, laws hold for arbitrary elements a, b, c, …. of ?? . 
(5.1) (A.1) ?? +?? =?? +?? (Commutative law for Addition)  
         (?? .2)?? +(?? +?? )=(?? +?? )+?? ( Associative law for Addition) 
          (A.3) For any two elements ?? ,?? ;3 always ?? satisiying the equation. 
?? +?? =?? 
(Inverse Law for addition) 
(M) a (bc) = (ab) c (Associative law for multiplication) 
(D) The two binary compositions are interrelated by the Distributive Law. 
?? (?? +?? )=???? +???? and (?? +?? )?? =???? +???? 
If we ignore the binary composition: multiplication in R, the laws (A.1), (A.2) and (A.3) 
assert that (?? ,+) is a commutative group. whose neutral element will be denoted by 0. 
0=?? -?? for all ?? ,?? +0=?? for all ?? 
(?? ,+) is called the underlying additive group of the ring. If, in addition to the laws (5.1), 
one has (5.2) (c) ???? = ba (Commutative law for multiplication). also, we say that ?? is a 
commutative ring. 
In a commutative ring either of the distributive laws is a consequence of the other. 
since we have studied, in detail, algebraic, structures with one binary composition, 
Groups, we can apply the results of Section to the additive group (?? 1
+?) of the ring. 
In particular, ?  precisely one element: 0 with the property   ?? +0=?? ?????? ?????? ?? ???? ?? 
(the null element or zero element of R) There exists precisely  one element -a such that 
?? +?? = ?? +(-?? )=0 for all ?? . 
Instead of ?? +(-?? ) we simply write ?? -?? . For a natural number =1,2 ,3… we put ?? .?? =
?? +?? +?+?? (?? terms) 
For a negative integer ?? ,=-1,-2,-3, ... we put ?? '
?? =(-?? ):?? =??¨·(-?? )=(-?? )+
?-?? )
'
.. .+(-?? ) (n terms)  
For the number 0 ; we put, for any ?? in ?? 
0.?? =0 (the zero-element of ?? ) 
The zero on the left side is a number whereas the zero on the right side is the null 
element of R : 
Then, if we put ?? = the set of all integers ={(0,±1,±2,…,±?? ;…} 
We have, for all ?? ,?? in ?? and ?? ,?? in ?? . 
(5.3) (?? +?? )?? =?? .?? +?? ·?? ,?? .(?? .?? )=(?? ?? )?? ,       ?? (?? +?? )=???? +???? 
It is easy to verify that 
a. (-?? )=-(???? );(-?? )·?? =-(???? );(-?? )(-?? )=?? .?? 
?? (?? -?? )=???? -???? ,(?? -?? )?? =???? -???? 
?? (?? 1
+?+?? ?? )=?? ?? 1
+?+?? ?? 1
 
(?? 1
+..+?? ?? )?? =?? 1
?? +?+?? ?? ?? 
 
(5.4) ?? ?? ·?? ?? =?? ?? ,?? =?? ?? ·?? ?? ,(?? ?? ,?? )
?? =?? ?? ,?? ?? (5.5) If ?? is a commutative ring, i.e., ab 
=ba for all ?? ,?? in ?? , then (???? )
?? =?? ?? ?? ?? ?? 
 
Example 
The set of complex numbers a + ib. 
?? ??? ,?? ??? forms a commutative ring, called the ring of Gaussian integers. 
[5:1] The ring of residue classes mod.m:Z(m) 
Let ?? >1 be a natural number. We write   ?? =?? (mod.?? ) if ?? divides ?? -?? (?? ,?? in ?? the 
set of all integers). Thus 
(5.6), ?? =?? (mod?? )?
 def 
?? |?? -?? 
We say; a is congruent to b (mod m). We have 
(i) ?? =?? , (ii) ?? =?? ??? =?? and  (iii) ?? =?? ,?? =?? ??? =0 
Congruence (mod m) is an equivalence relation. Denote the equivalence class 
containing , by [a]. It is" called the residue class (mod m) (We are keeping the modulus 
?? fixed). 
?? is partitioned into disjoint equivalence classes. 
Divide a and b by ?? : 
?? =???? +?? (0??? <?? )
?? =?? '
?? +?? '
 (0??? '
<?? )
 (?? -?? )=(?? -?? '
)·?? +(?? -?? '
)
?? |(?? -?? )??? |(?? -?? '
)
 
Owing to 0??? <?? , and 0??? '
<?? ; we have -?? <?? -?? <?? 1
 
i.e. |?? -?? '
|<?? Hence,  ?? |?? -?? '
??? -?? '
=0,?? =?? '
 
thus 
 
(5.7) a=b (mod.m) ??? and b leave the same remainder when divided by the modulus 
?? . 
All those a in z that leave one and the same remainder will form one equivalence class. 
(5.8)  ?? =?? 0
+?? 1
+?+?? ?? -1
 
?? ?? ={?? ??? : a leaves the remainder ?? ,  when divided by ?? }(?? =0,1,…,?? -1) 
If we denote by the residue class mod m we can thus write  (5.9)  ?? =0
¯
+1
¯
+?+
(?? -1)
?
 
observe that, if ?? is the remainder obtained when ' ?? ' is divided by ?? 1
 ' 
?? =?? .?? +?? , then (?? -?? )=?? .?? , i.e., ?? |?? -?? 
(5.10) i.e.,  ?? = (mod m) 
every number is congruent to its remainder. 
Page 4


Edurev123 
SECTION - II 
RINGS 
5. RINGS AND IDEALS 
In groups, we had a set and an algebraic structure with ONE binary composition defined 
on it. Now we consider algebraic structures with two binary compositions: 1
°
 Addition, 
and 2
°
 Multiplication denoted respectively by + and . 
Let ?? be a non-ernpty set, such that, given any two elements ?? and ?? in ?? there 
corresponds in R a  well-defined element a+b called their sum, and a well-defined 
element a.b, called their product. 
1
°
?? ×?? ???         2
°
?? ×?? ??? 
(?? ,?? )??? +??        (?? ,?? )??? .?? 
        Addition                   Multiplication 
We call R a ring if the following, laws hold for arbitrary elements a, b, c, …. of ?? . 
(5.1) (A.1) ?? +?? =?? +?? (Commutative law for Addition)  
         (?? .2)?? +(?? +?? )=(?? +?? )+?? ( Associative law for Addition) 
          (A.3) For any two elements ?? ,?? ;3 always ?? satisiying the equation. 
?? +?? =?? 
(Inverse Law for addition) 
(M) a (bc) = (ab) c (Associative law for multiplication) 
(D) The two binary compositions are interrelated by the Distributive Law. 
?? (?? +?? )=???? +???? and (?? +?? )?? =???? +???? 
If we ignore the binary composition: multiplication in R, the laws (A.1), (A.2) and (A.3) 
assert that (?? ,+) is a commutative group. whose neutral element will be denoted by 0. 
0=?? -?? for all ?? ,?? +0=?? for all ?? 
(?? ,+) is called the underlying additive group of the ring. If, in addition to the laws (5.1), 
one has (5.2) (c) ???? = ba (Commutative law for multiplication). also, we say that ?? is a 
commutative ring. 
In a commutative ring either of the distributive laws is a consequence of the other. 
since we have studied, in detail, algebraic, structures with one binary composition, 
Groups, we can apply the results of Section to the additive group (?? 1
+?) of the ring. 
In particular, ?  precisely one element: 0 with the property   ?? +0=?? ?????? ?????? ?? ???? ?? 
(the null element or zero element of R) There exists precisely  one element -a such that 
?? +?? = ?? +(-?? )=0 for all ?? . 
Instead of ?? +(-?? ) we simply write ?? -?? . For a natural number =1,2 ,3… we put ?? .?? =
?? +?? +?+?? (?? terms) 
For a negative integer ?? ,=-1,-2,-3, ... we put ?? '
?? =(-?? ):?? =??¨·(-?? )=(-?? )+
?-?? )
'
.. .+(-?? ) (n terms)  
For the number 0 ; we put, for any ?? in ?? 
0.?? =0 (the zero-element of ?? ) 
The zero on the left side is a number whereas the zero on the right side is the null 
element of R : 
Then, if we put ?? = the set of all integers ={(0,±1,±2,…,±?? ;…} 
We have, for all ?? ,?? in ?? and ?? ,?? in ?? . 
(5.3) (?? +?? )?? =?? .?? +?? ·?? ,?? .(?? .?? )=(?? ?? )?? ,       ?? (?? +?? )=???? +???? 
It is easy to verify that 
a. (-?? )=-(???? );(-?? )·?? =-(???? );(-?? )(-?? )=?? .?? 
?? (?? -?? )=???? -???? ,(?? -?? )?? =???? -???? 
?? (?? 1
+?+?? ?? )=?? ?? 1
+?+?? ?? 1
 
(?? 1
+..+?? ?? )?? =?? 1
?? +?+?? ?? ?? 
 
(5.4) ?? ?? ·?? ?? =?? ?? ,?? =?? ?? ·?? ?? ,(?? ?? ,?? )
?? =?? ?? ,?? ?? (5.5) If ?? is a commutative ring, i.e., ab 
=ba for all ?? ,?? in ?? , then (???? )
?? =?? ?? ?? ?? ?? 
 
Example 
The set of complex numbers a + ib. 
?? ??? ,?? ??? forms a commutative ring, called the ring of Gaussian integers. 
[5:1] The ring of residue classes mod.m:Z(m) 
Let ?? >1 be a natural number. We write   ?? =?? (mod.?? ) if ?? divides ?? -?? (?? ,?? in ?? the 
set of all integers). Thus 
(5.6), ?? =?? (mod?? )?
 def 
?? |?? -?? 
We say; a is congruent to b (mod m). We have 
(i) ?? =?? , (ii) ?? =?? ??? =?? and  (iii) ?? =?? ,?? =?? ??? =0 
Congruence (mod m) is an equivalence relation. Denote the equivalence class 
containing , by [a]. It is" called the residue class (mod m) (We are keeping the modulus 
?? fixed). 
?? is partitioned into disjoint equivalence classes. 
Divide a and b by ?? : 
?? =???? +?? (0??? <?? )
?? =?? '
?? +?? '
 (0??? '
<?? )
 (?? -?? )=(?? -?? '
)·?? +(?? -?? '
)
?? |(?? -?? )??? |(?? -?? '
)
 
Owing to 0??? <?? , and 0??? '
<?? ; we have -?? <?? -?? <?? 1
 
i.e. |?? -?? '
|<?? Hence,  ?? |?? -?? '
??? -?? '
=0,?? =?? '
 
thus 
 
(5.7) a=b (mod.m) ??? and b leave the same remainder when divided by the modulus 
?? . 
All those a in z that leave one and the same remainder will form one equivalence class. 
(5.8)  ?? =?? 0
+?? 1
+?+?? ?? -1
 
?? ?? ={?? ??? : a leaves the remainder ?? ,  when divided by ?? }(?? =0,1,…,?? -1) 
If we denote by the residue class mod m we can thus write  (5.9)  ?? =0
¯
+1
¯
+?+
(?? -1)
?
 
observe that, if ?? is the remainder obtained when ' ?? ' is divided by ?? 1
 ' 
?? =?? .?? +?? , then (?? -?? )=?? .?? , i.e., ?? |?? -?? 
(5.10) i.e.,  ?? = (mod m) 
every number is congruent to its remainder. 
The following laws hold for congruences: the proofs are omitted (they are easy 
consequences of the definitions)    
(5.11) 
?? 1
=?? 1
( mod m) |?? 1
+?? 2
=?? 1
+?? 2
( mod. ?? )  
?? 2
=?? 2
(mod.?? )??? 1
-?? 2
=?? 1
-?? 2
(mod.?? )  
?? 1
?? 2
??? 1
?? 2
 (mod.m)  
For example, let us verify that ?? 1
?? 2
=?? 1
?? 2
 ?? 2
?? 2
-?? 1
?? 2
=?? 1
(?? 2
-?? 2
)+?? 2
(?? 1
-?? 1
) 
Since ?? (?? 1
-?? 1
) , and (?? 2
-?? 2
) , it follows ?? 1
(?? 1
?? 2
-?? 1
?? 2
) 
By induction (5.12)  ?? ?? =?? ?? (mod.?? ),(?? =1,…,?? ) 
=?? 1
?? 2
…?? ?? =?? 1
?? 2
…?? ?? (mod?? ) 
In particular (5:13) 
?? ??? (mod?? )?|?? ?? ?? )
?? (mod?? )(?? =2,?? )  
 
CANCELLATION LAW 
(5.14) ax????? (mod ?? ) 
            (?? ,?? )=1 
[5:2] 
 In a congruence (mod a common fictor 
 can be cancelled, provided it is relatively 
 prime to the modulus. 
 
 )
 
Notation: (a, m) denotes the g.c.d. the greatest common divisor of (a, m). 
In fact, ax????? (mod ?? )=?? |???? -???? | 
It follows that, provided (?? ,?? )=1, m |?? (?? -?? )| 
 
Example 31: a) Show that, if ?? is a prime and plab, then either p|a or p|b   
b) If ?? |???? and (?? ,?? )=1, then m|b  
Page 5


Edurev123 
SECTION - II 
RINGS 
5. RINGS AND IDEALS 
In groups, we had a set and an algebraic structure with ONE binary composition defined 
on it. Now we consider algebraic structures with two binary compositions: 1
°
 Addition, 
and 2
°
 Multiplication denoted respectively by + and . 
Let ?? be a non-ernpty set, such that, given any two elements ?? and ?? in ?? there 
corresponds in R a  well-defined element a+b called their sum, and a well-defined 
element a.b, called their product. 
1
°
?? ×?? ???         2
°
?? ×?? ??? 
(?? ,?? )??? +??        (?? ,?? )??? .?? 
        Addition                   Multiplication 
We call R a ring if the following, laws hold for arbitrary elements a, b, c, …. of ?? . 
(5.1) (A.1) ?? +?? =?? +?? (Commutative law for Addition)  
         (?? .2)?? +(?? +?? )=(?? +?? )+?? ( Associative law for Addition) 
          (A.3) For any two elements ?? ,?? ;3 always ?? satisiying the equation. 
?? +?? =?? 
(Inverse Law for addition) 
(M) a (bc) = (ab) c (Associative law for multiplication) 
(D) The two binary compositions are interrelated by the Distributive Law. 
?? (?? +?? )=???? +???? and (?? +?? )?? =???? +???? 
If we ignore the binary composition: multiplication in R, the laws (A.1), (A.2) and (A.3) 
assert that (?? ,+) is a commutative group. whose neutral element will be denoted by 0. 
0=?? -?? for all ?? ,?? +0=?? for all ?? 
(?? ,+) is called the underlying additive group of the ring. If, in addition to the laws (5.1), 
one has (5.2) (c) ???? = ba (Commutative law for multiplication). also, we say that ?? is a 
commutative ring. 
In a commutative ring either of the distributive laws is a consequence of the other. 
since we have studied, in detail, algebraic, structures with one binary composition, 
Groups, we can apply the results of Section to the additive group (?? 1
+?) of the ring. 
In particular, ?  precisely one element: 0 with the property   ?? +0=?? ?????? ?????? ?? ???? ?? 
(the null element or zero element of R) There exists precisely  one element -a such that 
?? +?? = ?? +(-?? )=0 for all ?? . 
Instead of ?? +(-?? ) we simply write ?? -?? . For a natural number =1,2 ,3… we put ?? .?? =
?? +?? +?+?? (?? terms) 
For a negative integer ?? ,=-1,-2,-3, ... we put ?? '
?? =(-?? ):?? =??¨·(-?? )=(-?? )+
?-?? )
'
.. .+(-?? ) (n terms)  
For the number 0 ; we put, for any ?? in ?? 
0.?? =0 (the zero-element of ?? ) 
The zero on the left side is a number whereas the zero on the right side is the null 
element of R : 
Then, if we put ?? = the set of all integers ={(0,±1,±2,…,±?? ;…} 
We have, for all ?? ,?? in ?? and ?? ,?? in ?? . 
(5.3) (?? +?? )?? =?? .?? +?? ·?? ,?? .(?? .?? )=(?? ?? )?? ,       ?? (?? +?? )=???? +???? 
It is easy to verify that 
a. (-?? )=-(???? );(-?? )·?? =-(???? );(-?? )(-?? )=?? .?? 
?? (?? -?? )=???? -???? ,(?? -?? )?? =???? -???? 
?? (?? 1
+?+?? ?? )=?? ?? 1
+?+?? ?? 1
 
(?? 1
+..+?? ?? )?? =?? 1
?? +?+?? ?? ?? 
 
(5.4) ?? ?? ·?? ?? =?? ?? ,?? =?? ?? ·?? ?? ,(?? ?? ,?? )
?? =?? ?? ,?? ?? (5.5) If ?? is a commutative ring, i.e., ab 
=ba for all ?? ,?? in ?? , then (???? )
?? =?? ?? ?? ?? ?? 
 
Example 
The set of complex numbers a + ib. 
?? ??? ,?? ??? forms a commutative ring, called the ring of Gaussian integers. 
[5:1] The ring of residue classes mod.m:Z(m) 
Let ?? >1 be a natural number. We write   ?? =?? (mod.?? ) if ?? divides ?? -?? (?? ,?? in ?? the 
set of all integers). Thus 
(5.6), ?? =?? (mod?? )?
 def 
?? |?? -?? 
We say; a is congruent to b (mod m). We have 
(i) ?? =?? , (ii) ?? =?? ??? =?? and  (iii) ?? =?? ,?? =?? ??? =0 
Congruence (mod m) is an equivalence relation. Denote the equivalence class 
containing , by [a]. It is" called the residue class (mod m) (We are keeping the modulus 
?? fixed). 
?? is partitioned into disjoint equivalence classes. 
Divide a and b by ?? : 
?? =???? +?? (0??? <?? )
?? =?? '
?? +?? '
 (0??? '
<?? )
 (?? -?? )=(?? -?? '
)·?? +(?? -?? '
)
?? |(?? -?? )??? |(?? -?? '
)
 
Owing to 0??? <?? , and 0??? '
<?? ; we have -?? <?? -?? <?? 1
 
i.e. |?? -?? '
|<?? Hence,  ?? |?? -?? '
??? -?? '
=0,?? =?? '
 
thus 
 
(5.7) a=b (mod.m) ??? and b leave the same remainder when divided by the modulus 
?? . 
All those a in z that leave one and the same remainder will form one equivalence class. 
(5.8)  ?? =?? 0
+?? 1
+?+?? ?? -1
 
?? ?? ={?? ??? : a leaves the remainder ?? ,  when divided by ?? }(?? =0,1,…,?? -1) 
If we denote by the residue class mod m we can thus write  (5.9)  ?? =0
¯
+1
¯
+?+
(?? -1)
?
 
observe that, if ?? is the remainder obtained when ' ?? ' is divided by ?? 1
 ' 
?? =?? .?? +?? , then (?? -?? )=?? .?? , i.e., ?? |?? -?? 
(5.10) i.e.,  ?? = (mod m) 
every number is congruent to its remainder. 
The following laws hold for congruences: the proofs are omitted (they are easy 
consequences of the definitions)    
(5.11) 
?? 1
=?? 1
( mod m) |?? 1
+?? 2
=?? 1
+?? 2
( mod. ?? )  
?? 2
=?? 2
(mod.?? )??? 1
-?? 2
=?? 1
-?? 2
(mod.?? )  
?? 1
?? 2
??? 1
?? 2
 (mod.m)  
For example, let us verify that ?? 1
?? 2
=?? 1
?? 2
 ?? 2
?? 2
-?? 1
?? 2
=?? 1
(?? 2
-?? 2
)+?? 2
(?? 1
-?? 1
) 
Since ?? (?? 1
-?? 1
) , and (?? 2
-?? 2
) , it follows ?? 1
(?? 1
?? 2
-?? 1
?? 2
) 
By induction (5.12)  ?? ?? =?? ?? (mod.?? ),(?? =1,…,?? ) 
=?? 1
?? 2
…?? ?? =?? 1
?? 2
…?? ?? (mod?? ) 
In particular (5:13) 
?? ??? (mod?? )?|?? ?? ?? )
?? (mod?? )(?? =2,?? )  
 
CANCELLATION LAW 
(5.14) ax????? (mod ?? ) 
            (?? ,?? )=1 
[5:2] 
 In a congruence (mod a common fictor 
 can be cancelled, provided it is relatively 
 prime to the modulus. 
 
 )
 
Notation: (a, m) denotes the g.c.d. the greatest common divisor of (a, m). 
In fact, ax????? (mod ?? )=?? |???? -???? | 
It follows that, provided (?? ,?? )=1, m |?? (?? -?? )| 
 
Example 31: a) Show that, if ?? is a prime and plab, then either p|a or p|b   
b) If ?? |???? and (?? ,?? )=1, then m|b  
Solution 
a) Let ?? |a; we show: ?? |. Since ?? ? ?? ,(2,?? ) =1. 
Hence ??? ,?? such that 
1=???? +????
?? =(???? )?? +?? (???? )
 
since p|r.h.s., it follows p|b 
b) Since (?? ,?? )=1,? integers u, v with  ???? +???? =1 
(???? )?? +?? (???? )=0 
since p|r.h.s., so m|b 
(5.15) 
 
The congruence ax = 1(mod?? ) is solvable if and only if (?? ,?? )=1. The solution is (mod 
m) uniquely determined. 
Proof: Necessary 
?a?? =1(mod?? )??? |???? -1??? .?? =???? -1 for some integer ?? ?a-?? .?? =1 
Hence if ?? =(?? ,?? ) , then ?? |?? ,?? |?? , so ?? |1, ?? =1 
Sufficient 
Let (?? ,?? )=1, then, ? integers ?? ,?? with ???? - km=1 
i.e., m|ax-1, a?? =1(mod?? ) 
Finally, if ?? and ?? ’ are two solutions of the congruence (5. 15), then 
???? =1mod?? ), ?? ?? '
=1(mod?? ) 
so that ???? =?? ?? '
(rod.?? ) 
Since (?? ,?? )=1, a can be cancelled. 
?? =a( mod.m ) 
i.e., (5.16) all the solutions lie in one and the same residue class (mod, m ). 
This is what we mean by saying that the solution is (mod m unique) 
In other words, we need only try  ?? =1,2,…,?? -1