DAA 36 – Divisibility, Division Algorithm and GCD as a Linear Combination | CS F364

This lecture is DAA 36 in the Design and Analysis of Algorithms (DAA) course (CS F364). It introduces some of the most important foundations of number theory used in algorithm design: divisibility, the division algorithm, the greatest common divisor (GCD), and the linear-combination characterization of gcd.

The lecture begins with the definition of divisibility for integers and develops several basic properties of divisibility, including transitivity, closure under linear combinations, and behavior under scaling.

The lecture then proves the division algorithm: for integers a and b with a positive, there exist unique integers q and r such that
b = qa + r, with 0 less than or equal to r less than a. The existence and uniqueness proof is carried out carefully using the least nonnegative element argument.

Next, the lecture introduces the greatest common divisor of two integers and proves an important structural theorem:

the gcd of b and c can be written in the form bx + cy for some integers x and y.

This is proved by considering the smallest positive integer in the set of all integer linear combinations of b and c.

The lecture further shows two equivalent characterizations of gcd:

it is the least positive value of the linear form bx + cy, and
it is the positive common divisor of b and c that is divisible by every common divisor.

Finally, the result is generalized from two integers to multiple integers, showing that the gcd of b1, b2, ..., bn can also be expressed as an integer linear combination of these numbers.

This lecture provides the theoretical foundation needed for later number-theoretic algorithms such as the Euclidean Algorithm and modular arithmetic techniques.

📌 Topics Covered in This Lecture

Divisibility of integers

Basic properties of divisibility

Division algorithm

Existence and uniqueness of quotient and remainder

Greatest common divisor (GCD)

Common divisors and greatest common divisor

GCD as a linear combination

Least positive linear combination characterization

GCD for multiple integers

🎯 Who Should Watch

Students studying Design and Analysis of Algorithms

B.Tech / BE / M.Sc. / MCA / GATE aspirants

Learners studying number theory for algorithms

Anyone seeking a clear understanding of divisibility, gcd, and linear combinations

🔗 Playlist

This video is part of the playlist:
Design and Analysis of Algorithms – Complete DAA Course

Видео DAA 36 – Divisibility, Division Algorithm and GCD as a Linear Combination | CS F364 канала Abhishek Mishra – Mathematics & TCS