Euclidean algorithm — GCD computation — Hinglish notes

2.5.7 · Maths › Number Theory (Intermediate)

What is the Euclidean Algorithm?

Yeh kaam kyun karta hai? Algorithm ki neenv ek key property par tikhi hai:

How to Execute the Algorithm

Step-by-step:

Do integers $a \geq b > 0$ se shuru karo.
$r = a mod b$ compute karo.
Agar $r = 0$ hai, toh $b$ ko GCD ke roop mein output karo aur ruko.
Warna, $a \leftarrow b$ aur $b \leftarrow r$ replace karo, phir step 2 se repeat karo.

Yeh terminate kyun hota hai? Har iteration mein $b$ strictly decrease hota hai (kyunki $r < b$ ), aur $b$ hamesha non-negative rehta hai. Finite steps ke baad, $r$ zero ho jaata hai.

Time Complexity and Efficiency

Euclidean algorithm kitne steps leta hai?

Practical implication: 1000-digit numbers ke liye, algorithm roughly $5000$ steps leta hai—computer par easily computable. Compare karo factoring se, jo exponentially hard hai.

Extended Euclidean Algorithm (Preview)

Basic algorithm $g cd (a, b)$ nikaalti hai. Extended Euclidean algorithm integers $x, y$ bhi nikaalti hai jaise ki: $a x + b y = g cd (a, b)$

Yeh Bézout's identity hai aur in cheezoon ke liye crucial hai:

Modular inverses nikaalana (RSA cryptography mein use hota hai)
Linear Diophantine equations solve karna
LCM compute karna $lcm (a, b) = \frac{ab}{g c d ( a , b )}$ use karke

(Yeh agale note mein cover kiya gaya hai.)

Active Recall Practice

Recall Ek 12-saal ke bacche ko samjhao

Socho tumhare paas do chocolate bars hain: ek mein 48 squares hain, doosre mein 18. Tum inhe sabse bade equal pieces mein todna chahte ho jo dono bars mein perfectly fit hon (koi leftover nahi).

Guessing karne ki jagah, leftover trick use karo: badi bar (48) ko chhoti bar (18) ko measuring stick ki tarah use karke todo. Tumhe 2 poori chhoti bars milti hain aur 12 squares bach jaate hain. Ab 48 bhool jao—bas poochho: "18 aur 12 dono mein sabse bada piece kaun sa fit hoga?"

Repeat karo: 18 ko 12 se use karne par ek poori bar aur 6 bach jaate hain. Ab: "12 aur 6 dono mein kya fit hoga?" Yeh easy hai—6, 12 mein exactly do baar fit hota hai, 0 leftover ke saath. Ho gaya! Answer hai 6 squares.

Kaam kyun karta hai? Koi bhi piece jo dono original bars mein fit ho, usse leftovers mein bhi ZAROOR fit hona chahiye. Toh tum chhote aur chhote numbers ke saath kaam karte reh sakte ho jab tak aur divide na ho sake. Aakhri number hi tumhara answer hai.

Connections

2.5.01-divisibility-and-division-algorithm — Division algorithm $a = b q + r$ , Euclidean algorithm ka engine hai
2.5.03-fundamental-theorem-of-arithmetic — GCD, common prime factors se relate karta hai, lekin Euclidean algorithm factorization ko bypass karta hai
2.5.08-extended-euclidean-algorithm — Agla step: Bézout coefficients $a x + b y = g cd (a, b)$ nikaalana
2.5.10-bezouts-identity — Existence guarantee jo Euclidean algorithm exploit karta hai
2.5.15-modular-arithmetic-basics — GCD, modular inverses nikaalane ki key hai
3.2.04-rsa-encryption — RSA, key generation ke liye modular inverses compute karne mein Euclidean algorithm use karta hai
1.4.09-fibonacci-sequence — Euclidean algorithm ke worst-case inputs consecutive Fibonacci numbers hote hain

#flashcards/maths

Euclidean algorithm kya hai? :: Ek recursive method jo $g cd (a, b)$ nikaalti hai, $(a, b)$ ko baar baar $(b, a mod b)$ se replace karke jab tak $b = 0$ na ho jaye.

State the Euclidean Lemma :: $g cd (a, b) = g cd (b, a mod b)$ kisi bhi $b \neq = 0$ ke liye.

$g cd (a, b) = g cd (b, a mod b)$ kyun hota hai? :: Kyunki $a$ aur $b$ ka koi bhi common divisor $r = a - b q$ (remainder) ko bhi divide karta hai, aur vice versa. Toh common divisors ka set identical hota hai.

Euclidean algorithm ki termination condition kya hai?

Jab

b = 0

ho, algorithm ruk jaata hai aur

a

GCD hota hai.

n

digits tak ke inputs ke liye Euclidean algorithm kitne steps leta hai?

Zyada se zyada

O (n)

steps, specifically Lamé's Theorem se

\leq 5 n

. Input size ke terms mein yeh

O (lo g b)

hai.

Euclidean algorithm ke liye worst-case (maximum steps) inputs kaun se hain?

Consecutive Fibonacci numbers, jahaan har quotient 1 hota hai, jisse remainders ki shrinkage sabse slow hoti hai.

Euclidean algorithm se $g cd (48, 18)$ compute karo :: $48 = 18 \cdot 2 + 12$ , $18 = 12 \cdot 1 + 6$ , $12 = 6 \cdot 2 + 0$ . Answer: $6$ .

Sach ya jhooth: Euclidean algorithm kaam karne ke liye $a > b$ zaroori hai :: Jhooth. Agar $a < b$ ho, toh pehla step automatically unhe swap kar deta hai: $g cd (a, b) = g cd (b, a)$ .

LCM ka GCD se kya relation hai?

lcm (a, b) = \frac{ab}{g c d ( a , b )}

. Euclidean algorithm GCD nikaalti hai, jo phir LCM deta hai.

Bade numbers ke liye Euclidean algorithm prime factorization se faster kyun hai?

Factorization digits ki sankhya mein exponential hai; Euclidean algorithm polynomial hai (logarithmic steps), jo ise cryptography mein use hone wale 100+ digit numbers ke liye feasible banata hai.

Euclidean algorithm — GCD computation