Mathematics – I for CSE Stream 2024-25

Self Study
Module 4:
Division Algorithm: For any two given integers 𝑎, 𝑏 with 𝑏 ≥ 0, there exist unique integers 𝑞 and 𝑟 such that
𝑎 = 𝑞𝑏 + 𝑟, 0≤𝑟<𝑏.
That is, 𝑞 is the quotient 𝑟 reminder when you divide 𝑎 by 𝑏 .
𝑞
𝑏 𝑎
𝑏𝑞
𝑟

Examples:
1. 𝑎 = 37, 𝑏 = 7, 5
37 = 5 × 7 + 2 7 37
35
2

2. 𝑎 = −33, 𝑏 = 5 −7
−33 = −7 × 5 + 2 5 −33
−35
2

Clearly if 𝑏 = 2, either 𝑟 = 0 or 𝑟 = 1 .
Then integer of the form 𝑎 = 2𝑞 is called even, and 𝑎 = 2𝑞 + 1 is called odd.
Use the division algorithm to establish
i) Every odd integer is either of the form 4𝑘 + 1 or 4𝑘 + 3 .
ii) Square of any integer is either of the form 3𝑘 or 3𝑘 + 1 .
iii) Cube of any integer is either of the form 9𝑘 , 9𝑘 + 1 or 9𝑘 + 8.
Proof: i) Let 𝑎 be any odd integer. Then 𝑎 = 2𝑞 + 1 for some integer 𝑞.
Here 𝑞 maybe even or odd.
If 𝑞 is even, then 𝑞 = 2𝑘 for some integer 𝑘.
⟹ 𝑎 = 2(2𝑘) + 1 = 4𝑘 + 1.
If 𝑞 is odd, then 𝑞 = 2𝑘 + 1 for some integer 𝑘.
⟹ 𝑎 = 2(2𝑘 + 1) + 1 = 4𝑘 + 3.
ii) Square of any integer is either of the form 3𝑘 or 3𝑘 + 1 .
If the divisor 𝑏 = 3, reminder 𝑟 = 0,1 or 2.
Therefore any integer 𝑎 can be written as 𝑎 = 3𝑞 , 𝑎 = 3𝑞 + 1 or 𝑎 = 3𝑞 + 2 .
Then, 𝑎2 = (3𝑞)2 = 3(3𝑞 2 ) = 3𝑘.
Mathematics – I for CSE Stream 2024-25
𝑎 = (3𝑞 + 1)2 = 9𝑞 2 + 6𝑞 + 1 = 3(3𝑞 2 + 2𝑞) + 1 = 3𝑘 + 1.
2

Or 𝑎2 = (3𝑞 + 2)2 = 9𝑞 2 + 12𝑞 + 4 = 3(3𝑞 2 + 4𝑞 + 1) + 1 = 3𝑘 + 1.

Therefore square of any integer is either of the form 3𝑘 or 3𝑘 + 1 .
iii) Cube of any integer is either of the form 9𝑘 , 9𝑘 + 1 or 9𝑘 + 8.
If the divisor 𝑏 = 3, reminder 𝑟 = 0,1 or 2.
Therefore any integer 𝑎 can be written as 𝑎 = 3𝑞 , 𝑎 = 3𝑞 + 1 or 𝑎 = 3𝑞 + 2 .
⟹ 𝑎3 = (3𝑞)3 = 9(3𝑞 3 ) = 9𝑘.
𝑎3 = (3𝑞 + 1)3 = 9(3𝑞 3 ) + 9(3𝑞 2 ) + 9𝑞 + 1 = 9(3𝑞 3 + 3𝑞 2 + 𝑞) + 1 = 9𝑘 + 1.
Or, 𝑎3 = (3𝑞 + 2)3 = 9(3𝑞 3 ) + 9(6𝑞 2 ) + 9(2𝑞) + 8
= 9(3𝑞 3 + 6𝑞 2 + 2𝑞) + 8 = 9𝑘 + 8.
Therefore cube of any integer is either of the form 9𝑘 , 9𝑘 + 1 or 9𝑘 + 8.
Corollary: If 𝑎 and 𝑏 be any integers with 𝑏 ≠ 0, then there exists unique integers 𝑞 and 𝑟 such that 𝑎 = 𝑞𝑏 +
𝑟, 0 ≤ 𝑟 < |𝑏| .
Divisibility: An integer 𝑏 is said to be divisible by 𝑎 ≠ 0 , (or 𝑎 is said to be divisor of 𝑏 )
If 𝑏 = 𝑘𝑎 for some integer 𝑘, and is denoted by 𝑎|𝑏.
𝑎|𝑏 means 𝑎 is a divisor of 𝑏, 𝑎 is a factor of 𝑏 or 𝑏 is a multiple of 𝑎.
𝑎 ∤ 𝑏 indicate 𝑏 is not divisible by 𝑎.
Theorems: For any three integers 𝑎, 𝑏 and 𝑐,
i) 𝑎|0, 1|𝑎 and 𝑎|𝑎 for 𝑎 ≠ 0 .
ii) 𝑎|1 iff 𝑎 = ±1.
iii) If 𝑎|𝑏 and 𝑐|𝑑 then 𝑎𝑐|𝑏𝑑.
iv) If 𝑎|𝑏 and 𝑏|𝑐 then 𝑎|𝑐.
v) 𝑎|𝑏 and 𝑏|𝑎 iff 𝑎 = ±𝑏.
vi) If 𝑎|𝑏 and 𝑏 ≠ 0 then |𝑎| ≤ |𝑏|.
vii) If 𝑎|𝑏 and 𝑎|𝑐 then 𝑎|(𝑏𝑥 + 𝑐𝑦).
Zero is not the divisor of any integer, but any nonzero integer is divisor of zero.
Common Divisors: Let 𝑎 and 𝑏 are any two integers, an integer 𝑑 is said to be common divisor of 𝑎 and 𝑏 if
both 𝑑|𝑎 and 𝑑|𝑏 .
Greatest Common Divisor: Let 𝑎 and 𝑏 are any two integers with at least one of them is
nonzero. The greatest common divisor of 𝑎 and 𝑏 denoted by gcd(𝑎, 𝑏) is the positive
integer 𝑑 satisfying
1) 𝑑|𝑎 and 𝑑|𝑏 .
2) If 𝑐|𝑎 and 𝑐|𝑏 then 𝑐 ≤ 𝑑.
That is among the common divisors greatest one.
Theorem: For the given integers 𝑎 and 𝑏 with at least one of them is nonzero there exist two integers 𝑥, 𝑦 such
that gcd(𝑎, 𝑏) = 𝑎𝑥 + 𝑏𝑦 .
Prime: An integer 𝑝 > 1 is called prime number, if only the positive divisors of 𝑝 are 1, 𝑝.
Theorem: If 𝑝 is prime and 𝑝|𝑎𝑏, then 𝑝|𝑎 or 𝑝|𝑏.
Relatively prime: Two integers 𝑎 and 𝑏 with at least one of them is nonzero are said to be
relatively prime If gcd(𝑎, 𝑏) = 1.
Theorem: Two integers 𝑎 and 𝑏 with at least one of them is nonzero are said to be
Mathematics – I for CSE Stream 2024-25
relatively prime Iff there exist integers 𝑥, 𝑦 such that 1 = 𝑎𝑥 + 𝑏𝑦 .
𝑎 𝑏
Corollary: If gcd(𝑎, 𝑏) = 𝑑 , then gcd (𝑑 , ) = 1.
𝑑

Note: If 𝑎|𝑐 and 𝑏|𝑐 with gcd(𝑎, 𝑏) = 1, then 𝑎𝑏|𝑐 .

Theorem (Euclid’s Lemma): If 𝑎|𝑏𝑐 with gcd(𝑎, 𝑏) = 1 then 𝑎|𝑐 .
Theorem: Let 𝑎 and 𝑏 are two integers with at least one of them is nonzero, a positive integer 𝑑 = gcd(𝑎, 𝑏) if
and only if, 1) 𝑑|𝑎 and 𝑑|𝑏 and 2) If 𝑐|𝑎 and 𝑐|𝑏 then 𝑐|𝑑 .
That is any common divisor divides the greatest common divisor.
The Euclidean Algorithm:
If 𝑎 = 𝑞𝑏 + 𝑟, with 0 < 𝑟 < 𝑏, then gcd(𝑎, 𝑏) = gcd(𝑏, 𝑟)
Let 𝑎 and 𝑏 are two integers with at least one of them is nonzero.
Since gcd(𝑎, 𝑏) = gcd(−𝑎, 𝑏) = gcd(𝑎, −𝑏) = gcd(−𝑎, −𝑏), assume that 𝑎 ≥ 𝑏 > 0 .
By the division algorithm find 𝑞1 and 𝑟1 . 𝑎 = 𝑞1 𝑏 + 𝑟1 , where 0 ≤ 𝑟1 < 𝑏.
If 𝑟1 = 0, then gcd(𝑎, 𝑏) = 𝑏.
If 𝑟1 ≠ 0, then find 𝑞2 and 𝑟2 . 𝑏 = 𝑞2 𝑟1 + 𝑟2 , where 0 ≤ 𝑟2 < 𝑟1 .
If 𝑟2 = 0, then gcd(𝑎, 𝑏) = 𝑟1 .
If 𝑟2 ≠ 0, then find 𝑞3 and 𝑟3 . 𝑟1 = 𝑞3 𝑟2 + 𝑟3 , where 0 ≤ 𝑟3 < 𝑟2.
Continuing like this until zero remainder obtained.
Let 𝑟𝑛 = 0, then gcd(𝑎, 𝑏) = 𝑟𝑛−1 .
Example: Find the gcd(38, 178) , and express as linear combination of 38 and 178.

38 178 4
152
26 = 178 − (4)38
26 38 1
26
12 = 38 − (1)26
12 26 2
24
2 = 26 − (2)12
2 12 6
12
0

Theorem: gcd(𝑘𝑎, 𝑘𝑏) = 𝑘. gcd(𝑎, 𝑏), for any positive integer 𝑘.

Example: gcd(12, 30) = 6. gcd(2, 5) = 6.
Least common multiple: lcm(𝑎, 𝑏) is a positive integer 𝑚 satisfying
1) 𝑎|𝑚 and 𝑏|𝑚 .
2) If 𝑎|𝑐 and 𝑏|𝑐 then 𝑚|𝑐 .
Note:
1) gcd(𝑎, 𝑏) × lcm(𝑎, 𝑏) = 𝑎𝑏.
2) gcd(𝑎, 𝑏) = lcm(𝑎, 𝑏) if and only if 𝑎 = 𝑏. where 𝑎 and 𝑏 are nonzero integers.
3) If gcd(𝑎, 𝑏) = 1 and 𝑎|𝑐 and 𝑏|𝑐 then 𝑎𝑏|𝑐 .
Fundamental Theorem of Arithmetic: Every positive integer 𝑛 is a prime or a product of primes, and 𝑛 can be
represented uniquely in a canonical form.
Mathematics – I for CSE Stream 2024-25
𝑘 𝑘 𝑘
That is 𝑛 = 𝑝1 1 𝑝2 2 ⋯ ⋯ 𝑝𝑟 𝑟 , where 𝑘𝑖 ′s are positive integers, and 𝑝𝑖 ′s are primes with
𝑝1 < 𝑝2 < ⋯ < 𝑝𝑟 .
Examples: 360 = 23 × 32 × 5, 4725 = 33 × 52 × 7.

Module 5:
Solution of system of equations by Gauss-Jacobi iterative method and Inverse of a square
matrix by Cayley- Hamilton theorem
Gauss-Jacobi’s iteration method:
Consider the equations 𝑎1 𝑥 + 𝑏1 𝑦 + 𝑐1 𝑧 = 𝑑1 ; 𝑎2 𝑥 + 𝑏2 𝑦 + 𝑐2 𝑧 = 𝑑2 ; 𝑎3 𝑥 + 𝑏3 𝑦 + 𝑐3 𝑧 = 𝑑3 ,
If 𝑎1 , 𝑏2 , 𝑐3 are numerically large as compared to other coefficients in their respective equations.
Then iterative formula for 𝑥, 𝑦 𝑎𝑛𝑑 𝑧 are given by
1 1 1
𝑥 = 𝑎 (𝑑1 − 𝑏1 𝑦 − 𝑐1 𝑧) , 𝑦 = 𝑏 (𝑑2 − 𝑎2 𝑥 − 𝑐2 𝑥 ) and 𝑧 = 𝑐 (𝑑3 − 𝑎3 𝑥 − 𝑏3 𝑦) ⋯ ⋯ (1)
1 2 3

If not given assume that initial value of (𝑥, 𝑦, 𝑧) ≡ (0, 0, 0). Substitute these values in (1) and find
1 1 1
𝑥1 = 𝑎 (𝑑1 ) , 𝑦1 = 𝑏 (𝑑2 ) and 𝑧1 = 𝑐 (𝑑3 )
1 2 3

1 1 1
Then find, 𝑥2 = 𝑎 (𝑑1 − 𝑏1 𝑦1 − 𝑐1 𝑧1 ) , 𝑦2 = 𝑏 (𝑑2 − 𝑎2 𝑥1 − 𝑐2 𝑧1 ) and 𝑧2 = 𝑐 (𝑑3 − 𝑎3 𝑥1 − 𝑏3 𝑦1 )
1 2 3

Continuing like this using ,

1 1 1
𝑥𝑛+1 = 𝑎 (𝑑1 − 𝑏1 𝑦𝑛 − 𝑐1 𝑧𝑛 ) , 𝑦𝑛+1 = 𝑏 (𝑑2 − 𝑎2 𝑥𝑛 − 𝑐2 𝑧𝑛 ) and 𝑧𝑛+1 = 𝑐 (𝑑3 − 𝑎3 𝑥𝑛 − 𝑏3 𝑦𝑛 )
1 2 3

Until two set of values coincides.

Example:
1. Solve 54𝑥 + 𝑦 + 𝑧 = 110 , 2𝑥 + 15𝑦 + 6𝑧 = 72 , −𝑥 + 6𝑦 + 21𝑧 = 85
by Gauss-Jacobi’s iteration method by taking initial values (𝑥, 𝑦, 𝑧) ≡ (2, 3, 4).
1 1 1
𝑥𝑛+1 = 54 (110 − 𝑧𝑛 − 𝑦𝑛 ) 𝑦𝑛+1 = 15 (72 − 2𝑥𝑛 − 6𝑧𝑛 ) 𝑧𝑛+1 = 21 (85 − 6𝑦𝑛 + 𝑥𝑛 )

Let 𝑥0 = 2 𝑦0 = 3 𝑧0 = 4
1 1 1
𝑥1 = 54 (110 − 𝑧0 − 𝑦0 ) 𝑦1 = 15 (72 − 2𝑥0 − 6𝑧0 ) 𝑧1 = 21 (85 − 6𝑦0 + 𝑥0 )

= 1.907 = 2.933 = 3.286

1 1 1
𝑥2 = 54 (110 − 𝑧1 − 𝑦1 ) 𝑦2 = 15 (72 − 2𝑥1 − 6𝑧1 ) 𝑧2 = 21 (85 − 6𝑦1 + 𝑥1 )

= 1.922 = 3.231 = 3.300

1 1 1
𝑥3 = 54 (110 − 𝑧2 − 𝑦2 ) 𝑦3 = 15 (72 − 2𝑥2 − 6𝑧2 ) 𝑧3 = 21 (85 − 6𝑦2 + 𝑥2 )

=1.916 =3.224 =3.216

1 1 1
𝑥4 = 54 (110 − 𝑧3 − 𝑦3 ) 𝑦4 = 15 (72 − 2𝑥3 − 6𝑧3 ) 𝑧4 = 21 (85 − 6𝑦3 + 𝑥3 )

=1.918 =3.258 =3.218

Mathematics – I for CSE Stream 2024-25
1 1 1
𝑥5 = 54 (110 − 𝑧4 − 𝑦4 ) 𝑦5 = 15 (72 − 2𝑥4 − 6𝑧4 ) 𝑧5 = 21 (85 − 6𝑦4 + 𝑥4 )

=1.917 =3.257 =3.208

1 1 1
𝑥6 = 54 (110 − 𝑧5 − 𝑦5 ) 𝑦6 = 15 (72 − 2𝑥5 − 6𝑧5 ) 𝑧6 = 21 (85 − 6𝑦5 + 𝑥5 )

=1.917 =3.261 =3.208

∴ 𝑥 = 1.917 , 𝑦 = 3.261 𝑎𝑛𝑑 𝑧 = 3.208 .

2. Use Gauss-Jacobi’s iteration to solve 20𝑥 + 𝑦 − 2𝑧 = 17 , 3𝑥 + 20𝑦 − 𝑧 = 18 , 2𝑥 − 3𝑦 + 20𝑧 = 25 .
with 𝑥0 = 0, 𝑦0 = 0, 𝑧0 = 1 .
1 1 1
𝑥𝑛+1 = 20 (17 + 2𝑧𝑛 − 𝑦𝑛 ) 𝑦𝑛+1 = 20 (18 − 3𝑥𝑛 + 𝑧𝑛 ) 𝑧𝑛+1 = 20 (25 + 3𝑦𝑛 − 2𝑥𝑛+1 )

Let 𝑥0 = 0 𝑦0 = 0 𝑧0 = 1
1 1 1
𝑥1 = 20 (17 + 2𝑧0 − 𝑦0 ) 𝑦1 = 20 (18 − 3𝑥0 + 𝑧0 ) 𝑧1 = (25 + 3𝑦0 − 2𝑥0 )
= 0.95 20
= 0.95
= 1.25
1 1 1
𝑥2 = 20 (17 + 2𝑧1 − 𝑦1 ) 𝑦2 = 20 (18 − 3𝑥1 + 𝑧1 ) = 𝑧2 = (25 + 3𝑦1 − 2𝑥1 )
20
0.820
= 0.928
= 1.298
1 1 1
𝑥3 = 20 (17 + 2𝑧2 − 𝑦2 ) 𝑦3 = 20 (18 − 3𝑥2 + 𝑧2 ) 𝑧3 = (25 + 3𝑦2 − 2𝑥2 )
= 0.826 20
= 0.939
= 1.28
1 1 1
𝑥4 = 20 (17 + 2𝑧3 − 𝑦3 ) 𝑦4 = 20 (18 − 3𝑥3 + 𝑧3 ) 𝑧4 = (25 + 3𝑦3 − 2𝑥3 )
= 0.823 20
= 0.937
= 1.28

∴ 𝑥 = 0.937 , 𝑦 = 0.823 𝑎𝑛𝑑 𝑧 = 1.28 .

Cayley-Hamilton theorem: Every square matrix satisfies its characteristic equation.

3 1
Example: 1. Find the inverse of the matrix 𝐴 = [ ], by Cayley-Hamilton theorem.
2 4
Solution: Characteristic equation is |𝐴 − 𝜆𝐼| = 0 .
3−𝜆 1
⟹ | |=0
2 4−𝜆
⟹ 𝜆2 − 7𝜆 + 10 = 0 .
By Cayley-Hamilton theorem 𝐴2 − 7𝐴 + 10𝐼 = 0
⟹ 10𝐴−1 = 7𝐼 − 𝐴
1 7 0 3 1 1 4 −1
∴ 𝐴−1 = 10 {[ ]−[ ]} = 10 [ ].
0 7 2 4 −2 3
Mathematics – I for CSE Stream 2024-25
1 1 3
2. Find the inverse of the matrix 𝐴 = [1 5 1], by Cayley-Hamilton theorem.
3 1 1
Solution:
1 1 3
i) Let 𝐴 = [1 5 1] ∑ 𝐷 = 1 + 5 + 1 = 7.
3 1 1
Characteristic equation is |𝐴 − 𝜆𝐼| = 0 . ∑𝑀 𝐷 = 4 − 8 + 4 = 0
1−𝜆 1 3
| 1 5−𝜆 1 |=0 |𝐴| = −36
3 1 1−𝜆

⟹ 𝜆3 − ( 7 )𝜆2 + ( 0 )𝜆 − ( −36) = 0
⟹ 𝜆3 − 7𝜆2 + 0𝜆 + 36 = 0
By Cayley-Hamilton theorem 𝐴3 − 7𝐴2 + 36𝐼 = 0
⟹ 36𝐴−1 = 7𝐴 − 𝐴2
7 0 0 11 9 7 −4 −9 −7
1 1
∴ 𝐴−1 = 36 {[0 7 0] − [ 9 27 9 ]} = 36 [−9 −20 −9].
0 0 7 7 9 11 −7 −9 −4