Let 𝑁 be an integer, 𝑑 positive integer.

Then, there exists

𝑞 and 𝑟 such that
𝑁 = 𝑑𝑞 + 𝑟
0 ≤ 𝑟 < 𝑑.

GCD of 𝑥 and 𝑦: If 𝑑 = (𝑥, 𝑦), means, 𝑑|𝑥 and 𝑑|𝑦 and if

𝑒|𝑥 and 𝑒|𝑦, then 𝑒|𝑑.

Let 𝑀 and 𝑁 be two positive integers. Let 𝑀 > 𝑁 anld let

(𝑀, 𝑁) be the gcd of 𝑀 and 𝑁. Thus,
(𝑀, 𝑁) = (𝑁𝑞 + 𝑟1 , 𝑁) where 0 ≤ 𝑟1 < 𝑁.
(𝑀, 𝑁) = (𝑁𝑞 + 𝑟1 , 𝑁) = (𝑟1 , 𝑁) = ( 𝑟1 , 𝑟1 𝑞1 + 𝑟2 ),
0 ≤ 𝑟2 < 𝑟1 . Hence,
(𝑀, 𝑁) = ( 𝑟1 , 𝑟2 )
Problem: Find the GCD of 1189 and 2870.
(1189,2870) = (1189,492 ) = (205,492) = (205,82)
= (41,82) = 41.

Modular arithmetic:
Let 𝑚 be a fixed positive integer >1. We call two integers
𝑎 and 𝑏 are equivalent if 𝑚|𝑎 − 𝑏. If any integer is
divided by 𝑚, then the possible remainders are
0,1,2, … . , 𝑚 − 1. Let 𝑚 = 5. The possible rems. are
0,1,2,3,4. Consider the following sets:
𝑆0 = {… − 15, −10, −5, 0, 5, 10, 15, … }
𝑆1 = {… − 14, −9, −4, 1, 6, 11, 16, … }
𝑆2 = {… − 13, −8, −3, 2, 7, 12, 17, … }
𝑆3 = {… − 12, −7, −2, 3, 8, 13, 18, … }
𝑆4 = {… − 11, −6, −1, 4, 9, 14, 19, … }
The sets 𝑆0 , 𝑆1 , … , 𝑆4 constitute a disjoint partition of the
set of integers ℤ. The elements of set 𝑆𝑖 when divided by
5 leave remainder 4. Any two elements of 𝑆𝑖 are
equivalent w.r.to 𝑚 = 5. The set 𝑆𝑖 can be represented
by 𝑖̅ or simply by 𝑖 for 𝑖 = 0,1,2,3,4.
Definition: If 𝑎 and 𝑏 are two integers, we say that 𝑎 is
congruent to 𝑏 modulo 𝑚 if 𝑚|𝑎 − 𝑏 and is written as
𝑎 ≡ 𝑏 (mod 𝑚).
Thus, if 𝑎 ≡ 𝑏 (mod 𝑚), then both 𝑎 and 𝑏 leave the
same remainders when divided by 𝑚. Modulo 𝑚, if 𝑎 ≡
𝑏, we don’t distinguish between them and treat them
alike.
Theorem: For each fixed positive integer 𝑚, congruence
modulo 𝑚 is an equivalence relation.
Proof: Since 𝑚|𝑎 − 𝑎, 𝑎 ≡ 𝑎 (mod 𝑚). (Reflexive)
If 𝑎 ≡ 𝑏 (mod 𝑚), then 𝑚|𝑎 − 𝑏 and hence 𝑚|𝑏 − 𝑎.
This implies 𝑏 ≡ 𝑎 (mod 𝑚), Hence congruence modulo
𝑚 is symmetric.
If 𝑎 ≡ 𝑏 (mod 𝑚) and if 𝑏 ≡ 𝑐 (mod 𝑚) then 𝑚|𝑎 − 𝑏
and 𝑚|𝑏 − 𝑐. Hence 𝑚|(𝑎 − 𝑏) + (𝑏 − 𝑐 ) = 𝑎 − 𝑐.
Hence, 𝑚|𝑎 − 𝑐 which implies 𝑎 ≡ 𝑐 (mod 𝑚). Hence
congruence modulo 𝑚 is transitive.
Properties:
(1) If 𝑎 ≡ 𝑏 (mod 𝑚), then 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚).
(2) If 𝑎 ≡ 𝑏 (mod 𝑚), iff 𝑎 + 𝑐 ≡ 𝑏 + 𝑐 (mod 𝑚).
(3) The converse of (1) need not be true.
Assume that 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚). Then 𝑚|𝑎𝑐 − 𝑏𝑐 =
(𝑎 − 𝑏)𝑐, which does not imply that 𝑚|𝑎 − 𝑏. Let
𝑑 = (𝑐, 𝑚). Then, 𝑐 = 𝑑𝑘 and 𝑚 = 𝑑𝑙 for some 𝑘 and 𝑙
such that (𝑘, 𝑙 ) = 1, that is 𝑘 and 𝑙 are relatively
prime.
𝑚|(𝑎 − 𝑏)𝑐
Implies
𝑑𝑙|(𝑎 − 𝑏)𝑑𝑘
and hence 𝑙|(𝑎 − 𝑏)𝑘. But (𝑘, 𝑙 ) = 1 implies 𝑙|(𝑎 − 𝑏).
Hence, 𝑎 ≡ 𝑏 (mod 𝑙), that is,
𝑚
𝑎 ≡ 𝑏 (mod ) , 𝑑 = (𝑐, 𝑚).
𝑑
If (𝑐, 𝑚) = 1, then 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚) implies
𝑎 ≡ 𝑏 (mod 𝑚).
Note: 𝑚 is called the modulus of congruence.

Theorem: If 𝑎 ≡ 𝑏 (mod 𝑚), then 𝑎𝑘 ≡ 𝑏 𝑘 (mod 𝑚) for

𝑘 ≥ 1.
Proof: 𝑎 − 𝑏|𝑎𝑘 − 𝑏 𝑘 . Thus, 𝑎𝑘 − 𝑏 𝑘 = 𝑐(𝑎 − 𝑏) for
some positive integer 𝑐. Hence, 𝑚|𝑎 − 𝑏 => 𝑚|𝑎𝑘 − 𝑏 𝑘 .
Thus, if 𝑎 ≡ 𝑏 (mod 𝑚), then 𝑎𝑘 ≡ 𝑏 𝑘 (mod 𝑚) for 𝑘 ≥
1.
Theorem: If 𝑎 ≡ 𝑏 (mod 𝑚) and 𝑐 ≡ 𝑑 (mod 𝑚), then
𝑎 + 𝑐 ≡ 𝑏 + 𝑑 (mod 𝑚).
If 𝑓(𝑥) is a polynomial with integer coefficients, 𝑎 ≡
𝑏 (mod 𝑚), then 𝑓(𝑎) ≡ 𝑓 (𝑏)(mod 𝑚).
Q1. Find the remainder if 1021 is divided by 7.
Ans: 1021 ≡ 321 (mod 7). But, 321 = 277 ≡ (−1)7 =
−1 ≡ 6(mod 7). Thus, 1021 ≡ 6(mod 7).
Q2. Find the digit in the unit place in the decimal
expansion of 4174 .
Ans: We will reduce 4174 modulo 10.
Observe that 4174 ≡ 174 = 1(mod 10).

Q3. Find the digit in the unit place in the decimal

expansion of 74674 .
Ans: 74674 ≡ 674 ≡ 6(mod 10).
Q4. Find the digit in the 10’s place in the decimal
expansion of 74674 .
Ans: 74674 ≡ 4674 ≡ (462 )37 = 211637 ≡ 1637 =
(163 )12 × 16 = 409612 × 16 ≡ (−4)12 × 16 = 414 ≡
256 × 1024^2 ≡ 56 × 242 ≡ (−44)(−24) ≡
56(mod 100).
The unit in the 10’s place is 5.
1999
Q5: Find the remainder when 19971998 is divided by
10.
1999 1999
Ans: 19971998 ≡ 71998 (𝑚𝑜𝑑 10).
70 ≡ 1(𝑚𝑜𝑑 10), 71 ≡ 7(𝑚𝑜𝑑 10), 72 ≡ 9(𝑚𝑜𝑑 10)
73 ≡ 3(𝑚𝑜𝑑 10), 74 ≡ 1(𝑚𝑜𝑑 10),
75 ≡ 7(𝑚𝑜𝑑 10), 76 ≡ 9(𝑚𝑜𝑑 10), 77 ≡ 3(𝑚𝑜𝑑 10).
1 𝑖𝑓 𝑥 ≡ 0(𝑚𝑜𝑑 4)
7 𝑖𝑓 𝑥 ≡ 1(𝑚𝑜𝑑 4)
7𝑥 ≡ {
9 𝑖𝑓 𝑥 ≡ 2(𝑚𝑜𝑑 4)
3 𝑖𝑓 𝑥 ≡ 3(𝑚𝑜𝑑 4).
1999
In 71998 , the exponent 𝑥 = 19981999 ≡ 21999 ≡
1999
0(𝑚𝑜𝑑 4). Hence, 71998 ≡ 1(𝑚𝑜𝑑 10).

Linear Diophantine Equations

Consider the equation 3𝑥 + 7𝑦 = 15. Here, we look for
integer solutions.
15 − 7𝑦
𝑥=
3
If 𝑦 = 0, then 𝑥 = 5, hence (5,0) is one solution. For
integer solution, 3|15 − 7𝑦, that is 7𝑦 ≡ 15(𝑚𝑜𝑑 3).
Thus, 7𝑦 ≡ 0(𝑚𝑜𝑑 3), that is 3|7𝑦=> 3|𝑦, hence,
𝑦 = 3𝑘, 𝑘 𝑖𝑠 𝑎𝑛𝑦 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 and then
3𝑥 + 7𝑦 = 15 => 3𝑥 + 21𝑘 = 15
Hence, 𝑥 = 5 − 7𝑘. So the general solution is
𝑥 = 5 − 7𝑘, 𝑦 = 3𝑘.
Consider the Diophantine equation
6𝑥 − 15𝑦 = 38.
Thus,
3(2𝑥 − 5𝑦) = 38 and hence 3|38 which is not true.
Hence, 6𝑥 − 15𝑦 = 38 has no solution.
The linear Diophantine equation 𝑎𝑥 + 𝑏𝑦 = 𝑐 and let
𝑑 = (𝑎, 𝑏). For the existence of solution, 𝑑|𝑐.

Example: 6𝑥 + 8𝑦 = 10 has solutions. Equivalent to

5−4𝑦
3𝑥 + 4𝑦 = 5. Hence, 𝑥 = => 4𝑦 ≡ 5(𝑚𝑜𝑑 3)
3

=> 𝑦 ≡ 2(𝑚𝑜𝑑 3) => 𝑦 = 3𝑘 + 2

Hence, 𝑥 = −1 − 4𝑘. For example, if 𝑘 = −5, then
𝑥 = 19, 𝑦 = −13.

Consider the LDE 2𝑥 − 3𝑦 + 𝑧 = 17

Let 𝑤 = 3𝑦 − 𝑧. Then, the original equation will take the
17+𝑤
form 2𝑥 − 𝑤 = 17, => 𝑥 = => 𝑤 ≡ −17 ≡
2
1(𝑚𝑜𝑑 2). Hence, 𝑤 = 2𝑘 + 1 and 𝑥 = 𝑘 + 9
Let 𝑛 be a positive integer. Consider this set
ℤ𝑛 = {0,1,2, … , 𝑛 − 1}.
Is this a group? Define the binary operation addition
modulo 𝑛. For example if 𝑛 = 10, then 7+5≡
2(𝑚𝑜𝑑 10). 8+9≡7 (mod 10). Closure law holds.
Associativity is obvious. (5+6)+7≡ 1 + 8 = 8(𝑚𝑜𝑑 10).
5 + (6 + 7) ≡ 5 + 3 = 8(𝑚𝑜𝑑 10). Identity element 0.
Inverse: 5−1 = −5 ≡ 5(𝑚𝑜𝑑 10). ℤ𝑛 is a commutative
group with binary operation addition modulo 𝑛. Consider
ℤ∗𝑛 = {1,2, … , 𝑛 − 1}.
Is this a group with binary operation multiplication
modulo 𝑛.
∗
ℤ10 = {1,2,3,4,5,6,7,8,9}
Observe that 2 × 5 ≡ 0(𝑚𝑜𝑑 10). Not a group. Failures:
Closure law, existence of inverses.
Let 𝑛 = 𝑝 be a prime. Consider
ℤ∗𝑝 = {1,2, … , 𝑝 − 1}.
Is it a group with multiplication modulo 𝑝?
Closure law: Observe that all elements of ℤ∗𝑝 are
relatively prime with 𝑝, that is 𝑝 does not divide any
element of ℤ∗𝑝 . If 𝑎, 𝑏 ∈ ℤ∗𝑝 , then 𝑝 divides none of 𝑎 and
𝑏 hence 𝑎𝑏 ∈ ℤ∗𝑝 . Closure law holds. Existence of
inverses? Since (𝑎, 𝑝) = 1 for all 𝑎 ∈ ℤ∗𝑝 , all have
inverses. Hence, ℤ∗𝑝 is a group with multiplication modulo
𝑝. What are the self-inverses? Observe that
1 × 1 ≡ 1(𝑚𝑜𝑑 𝑝)
and
(𝑝 − 1)(𝑝 − 1) ≡ 1.
Further, if 𝑥 2 ≡ 1(𝑚𝑜𝑑 𝑝), then 𝑝|(𝑥 + 1)(𝑥 − 1).
Hence, 𝑝|𝑥 + 1 or 𝑝|𝑥 − 1. Thus,
𝑥 ≡ −1 ≡ 𝑝 − 1(𝑚𝑜𝑑 𝑝) or 𝑥 ≡ 1(𝑚𝑜𝑑 𝑝). Thus, the
only self inverses are 1 and 𝑝 − 1. The other 𝑝 − 3
elements of ℤ∗𝑝 have inverses other than themselves.
𝑝−3
Now, we can form pairs using these 𝑝 − 3 elements,
2
we pair as (𝑥, 𝑥 −1 ). Then,
(𝑝 − 1)! = 1 ⋅ (𝑝 − 1) ⋅ 𝑋
Then 𝑋 ≡ 1(𝑚𝑜𝑑 𝑝). Hence,
(𝑝 − 1)! ≡ 1 ⋅ (𝑝 − 1) ≡ −1(𝑚𝑜𝑑 𝑝).
That is
𝑝|(𝑝 − 1)! + 1.
This happens even if 𝑝 = 2.
(Wilson’s Theorem)
Theorem: If 𝑝 is a prime then 𝑝|(𝑝 − 1)! + 1, that is
(𝑝 − 1)! ≡ −1 (𝑚𝑜𝑑 𝑝).

The converse of Wilson’s Theorem is also true.

If 𝑛 is a positive odd integer > 2 and 𝑛|(𝑛 − 1)! + 1,
then 𝑛 is a prime.
Primality test: Not used.
Q. Find the remainder when 1! + 2! + ⋯ + 37! is divided
by 11.
Discussion:
(𝑝 + 1)(𝑝 + 2) ⋯ (2𝑝 − 1) ≡ 1 ⋅ 2 ⋅ ⋯ ⋅ (𝑝 − 1)
≡ −1(𝑚𝑜𝑑 𝑝)
(2𝑝 + 1)(2𝑝 + 2) ⋯ (3𝑝 − 1) ≡ 1 ⋅ 2 ⋅ ⋯ ⋅ (𝑝 − 1) ≡
−1(𝑚𝑜𝑑 𝑝).
1! + 2! + ⋯ + 37!
1! + 2! + ⋯ + 10!
(𝑝 − 1)! ≡ −1 (𝑚𝑜𝑑 𝑝)
=>(𝑝 − 2)! (𝑝 − 1) ≡ −1 (𝑚𝑜𝑑 𝑝) => (𝑝 − 2)! (−1) ≡
−1 (𝑚𝑜𝑑 𝑝) => (𝑝 − 2)! ≡ 1 (𝑚𝑜𝑑 𝑝)
=> −2(𝑝 − 3)! ≡ 1(𝑚𝑜𝑑 𝑝) => 2(𝑝 − 3)!
≡ −1(𝑚𝑜𝑑 𝑝)
1! + 2! + ⋯ + 10! ≡ 1! + 2! + ⋯ + 8!
≡ 1 + 2 + 6 + 2 − 1 − 6 + 2 + 5 ≡ 0(𝑚𝑜𝑑 11)
Furthermore,
11! ≡ 0(𝑚𝑜𝑑 11)
12! ≡ 0(𝑚𝑜𝑑 11)
and so on. Hence,
1! + 2! + ⋯ + 37! ≡ 0(𝑚𝑜𝑑 11).
Suppose 5𝑥 ≡ 1(𝑚𝑜𝑑 7). Then 𝑥 ≡ 3(𝑚𝑜𝑑 7).
Here, 3 is the inverse of 5 modulo 7.

Now, modulo 𝑚, the numbers 0,1, … . , 𝑚 − 1 are called

the least residues. The set 𝑆 = {0,1, … . , 𝑚 − 1} is called
a complete residue system modulo 𝑚. For example,
modulo 𝑚, 𝑆 ′ = {2,3 … . , 𝑚, 𝑚 + 1} is also a complete
residue system. If 𝑝 is a prime, the set
𝑆𝑝 = {1,2, … , 𝑝 − 1}
Has the property that no element is divisible by 𝑝. That is
for each 𝑎 ∈ 𝑆𝑝 , (𝑎, 𝑝) = 1. Now let 𝑎 be any positive
integer such that (𝑎, 𝑝) = 1, that is 𝑝 does not divide 𝑎.
Now consider the set
𝑆𝑝 ′ = {𝑎, 2𝑎, … , (𝑝 − 1)𝑎}
(𝑘𝑎, 𝑝) = 1
Then the elements of 𝑆𝑝 ′ also form a complete residue
system modulo 𝑚. We claim that 𝑎, 2𝑎, … , (𝑝 − 1)𝑎 are
congruent to 1,2, … , 𝑝 − 1 in some way. Then,
𝑎 ⋅ 2𝑎 ⋅ ⋯ ⋅ (𝑝 − 1)𝑎 ≡ 1 ⋅ 2 ⋅ ⋯ ⋅ (𝑝 − 1) (𝑚𝑜𝑑 𝑝)
That is
(𝑝 − 1)! 𝑎𝑝−1 ≡ (𝑝 − 1)! (𝑚𝑜𝑑 𝑝)
Since ((𝑝 − 1)!, 𝑝) = 1, we can cancel (𝑝 − 1)! From
both sides of the congruence and hence
𝑎𝑝−1 ≡ 1(𝑚𝑜𝑑 𝑝).
The above discussion proves
Theorem (Fermat’s little theorem): If 𝑝 is a prime and 𝑎
ia an integer not divisible by 𝑝, then 𝑝|𝑎𝑝−1 − 1.

Corollary: If 𝑝 is a prime and 𝑎 is an integer then 𝑎𝑝 ≡

𝑎(𝑚𝑜𝑑 𝑝).
Proof: If 𝑝|𝑎, then 𝑎𝑝 − 𝑎 = 𝑎(𝑎𝑝−1 − 1) which is
divisible by 𝑝. If 𝑝 does not divide 𝑎, then 𝑝|𝑎𝑝−1 − 1.
Hence the conclusion follows.

Q. Find the remainder when 76375 is divided by 31.

Solution: 76375 ≡ 14375 (𝑚𝑜𝑑 31).
1430 = 1431−1 ≡ 1(𝑚𝑜𝑑 31)
by FLT. Hence,
14375 = 1415 × (1430 )12 ≡ 1415 = 14 × (142 )7
≡ 14 × 107 = 14 × 10 × (103 )2 ≡ 16 × 82
≡ 32 ≡ 1(𝑚𝑜𝑑 31).
Do the converse of Fermat’s little theorem true? That is,
if n is a positive integer and (𝑎, 𝑛) = 1, and 𝑎𝑛 ≡
𝑎(𝑚𝑜𝑑 𝑛), then is 𝑛 a prime? NO.
7−1
6 6
7|2 − 1. But 2 − 1 = 7 ⋅ 9. Thus, 7|2 2 − 1. Thus,
𝑝|𝑎𝑝−1 − 1 does not mean that 𝑝 − 1 is not the smallest
index with this property. Next,
212 ≡ 26 × 26 ≡ 1(𝑚𝑜𝑑 7)
Thus,
225−1 ≡ 212 × 212 ≡ 1(𝑚𝑜𝑑 7)