Extended Euclidean algorithm — Hinglish notes

2.5.8 · Maths › Number Theory (Intermediate)

Derivation from First Principles

Regular Algorithm Kaise Kaam Karta Hai

$a \geq b > 0$ se shuru karo. Euclidean algorithm ek sequence produce karta hai:

a b r_{1} r_{n - 2} r_{n - 1} = q_{1} b + r_{1} (0 \leq r_{1} < b) = q_{2} r_{1} + r_{2} (0 \leq r_{2} < r_{1}) = q_{3} r_{2} + r_{3} ⋮ = q_{n} r_{n - 1} + r_{n} = q_{n + 1} r_{n} + 0

Last non-zero remainder $r_{n}$ hi $g cd (a, b)$ hai.

Coefficients Ko Backwards Track Karna

Second-to-last equation se: $r_{n} = r_{n - 2} - q_{n} r_{n - 1}$ .

$r_{n - 1}$ ka expression upar wali line se substitute karo, phir $r_{n - 2}$ ka, aur aisa karte karte wapis $a$ aur $b$ tak jaao. Yeh substitution reveal karta hai ki $r_{n} = x \cdot a + y \cdot b$ kuch integers $x, y$ ke liye.

The Forward (Efficient) Method

Backtrack karne ki jagah, har step par coefficients $(x_{i}, y_{i})$ maintain karo jaise ki $r_{i} = x_{i} a + y_{i} b$ .

Base cases:

$r_{0} = a = 1 \cdot a + 0 \cdot b ⟹ (x_{0}, y_{0}) = (1, 0)$
$r_{1} = b = 0 \cdot a + 1 \cdot b ⟹ (x_{1}, y_{1}) = (0, 1)$

Recurrence: $r_{i} = r_{i - 2} - q_{i} r_{i - 1}$ se, humein milta hai: $r_{i} = (x_{i - 2} a + y_{i - 2} b) - q_{i} (x_{i - 1} a + y_{i - 1} b)$ $= (x_{i - 2} - q_{i} x_{i - 1}) a + (y_{i - 2} - q_{i} y_{i - 1}) b$

Yeh step kyun? Har remainder pichle do ka linear combination hota hai. Agar hum jaante hain pichle dono ko $a$ aur $b$ ke terms mein kaise likhte hain, toh naye ko bhi usi tarah likh sakte hain.

Worked Examples

Step	$r_{i - 2}$	$r_{i - 1}$	$q_{i}$	$r_{i}$	$x_{i - 2}$	$x_{i - 1}$	$x_{i} = x_{i - 2} - q_{i} x_{i - 1}$	$y_{i - 2}$	$y_{i - 1}$	$y_{i} = y_{i - 2} - q_{i} y_{i - 1}$
0	—	—	—	56	1	—	—	0	—	—
1	—	—	—	15	—	0	—	—	1	—
2	56	15	3	11	1	0	$1 - 3 \cdot 0 = 1$	0	1	$0 - 3 \cdot 1 = - 3$
3	15	11	1	4	0	1	$0 - 1 \cdot 1 = - 1$	1	-3	$1 - 1 \cdot (- 3) = 4$
4	11	4	2	3	1	-1	$1 - 2 \cdot (- 1) = 3$	-3	4	$- 3 - 2 \cdot 4 = - 11$
5	4	3	1	1	-1	3	$- 1 - 1 \cdot 3 = - 4$	4	-11	$4 - 1 \cdot (- 11) = 15$
6	3	1	3	0	—	—	—	—	—	—

Result: $g cd (56, 15) = 1$ , with $x = - 4$ , $y = 15$ .

Verification: $56 \cdot (- 4) + 15 \cdot 15 = - 224 + 225 = 1$ . ✓

Yeh step kyun? Har row naya remainder compute karta hai aur recurrence use karke coefficients update karta hai. Jab $r_{i} = 0$ ho jaata hai, pichli row answer deti hai.

Step	$r_{i - 2}$	$r_{i - 1}$	$q_{i}$	$r_{i}$	$x_{i}$	$y_{i}$
0	—	—	—	240	1	0
1	—	—	—	46	0	1
2	240	46	5	10	1 - 5·0 = 1	0 - 5·1 = -5
3	46	10	4	6	0 - 4·1 = -4	1 - 4·(-5) = 21
4	10	6	1	4	1 - 1·(-4) = 5	-5 - 1·21 = -26
5	6	4	1	2	-4 - 1·5 = -9	21 - 1·(-26) = 47
6	4	2	2	0	—	—

Result: $g cd (240, 46) = 2$ , with $x = - 9$ , $y = 47$ .

Check: $240 \cdot (- 9) + 46 \cdot 47 = - 2160 + 2162 = 2$ . ✓

Common Mistakes

Applications

Modular Inverse: $a^{- 1} (mod m)$ find karne ke liye (jab $g cd (a, m) = 1$ ho), $a$ aur $m$ par Extended Euclidean run karo. Coefficient $x$ jo $a x + m y = 1$ satisfy karta hai woh inverse hai: $a x \equiv 1 (mod m)$ .
Linear Diophantine Equations: $a x + b y = c$ solve karne ke liye, pehle $g cd (a, b)$ find karo. Agar $c$ , $g cd (a, b)$ ka multiple nahi hai, toh koi solution exist nahi karta. Warna, Bézout coefficients ko scale karo: agar $a x_{0} + b y_{0} = g cd (a, b)$ hai, toh $x = x_{0} \cdot (c / g cd (a, b))$ aur $y = y_{0} \cdot (c / g cd (a, b))$ ek particular solution hai.
RSA Cryptography: Private key $d$ compute karna jaise ki $e d \equiv 1 (mod ϕ (n))$ Extended Euclidean Algorithm use karta hai.

Diagram

Recall Feynman: Ek 12-saal ke bacche ko samjhao

Socho tumhare paas coins ki do dher hain, maano 56 aur 15. Regular Euclidean algorithm bilkul waisa hai jaise baar baar chhoti dher ko badi se hatate rehna jab tak tumhare paas sabse badi dher na bache jo dono ko divide kare (yeh gcd hai).

Ab, Extended version poochta hai: "Kya main original dono dher ke sizes ko addition aur subtraction se combine karke exactly yeh gcd bana sakta hoon?" Jawab hamesha haan hota hai! Algorithm ek running tally rakhta hai: "Ab tak, yeh remainder pehli dher ki __ copies aur doosri dher ki ___ copies se bana hai (jahan negative ka matlab hai hum subtract kar rahe hain)."

Ant mein, tumhe pata hota hai exactly kitni original dher add/subtract karni hai gcd paane ke liye. Wahi magic formula hai $a x + b y = g cd (a, b)$ aur yeh number theory mein har jagah use hota hai!

Connections

Euclidean Algorithm — "non-extended" version jo sirf $g cd (a, b)$ find karta hai
Bézout's Identity — theorem jo integer solutions $a x + b y = g cd (a, b)$ guarantee karta hai
Modular Multiplicative Inverse — Extended Euclidean se milta hai jab $g cd (a, m) = 1$ ho
Linear Diophantine Equations — Bézout coefficients scale karke solve hote hain
Chinese Remainder Theorem — apni construction mein modular inverses use karta hai
RSA Algorithm — private key calculation Extended Euclidean par depend karta hai

#flashcards/maths

Extended Euclidean Algorithm kya compute karta hai? :: Yeh $g cd (a, b)$ aur integers $x, y$ compute karta hai jaise ki $a x + b y = g cd (a, b)$ (Bézout's identity).

Coefficient recurrence ke base cases kya hain?

(x_{0}, y_{0}) = (1, 0)

for

r_{0} = a

ke liye, aur

(x_{1}, y_{1}) = (0, 1)

for

r_{1} = b

ke liye.

Extended Euclidean Algorithm mein

x_{i}

ki recurrence kya hai?

x_{i} = x_{i - 2} - q_{i} \cdot x_{i - 1}

, jahan

q_{i}

step

i

par quotient hai.

Extended Euclidean use karke $a$ ka modular inverse modulo $m$ kaise find karte hain? :: $a$ aur $m$ par Extended Euclidean run karo. Agar $g cd (a, m) = 1$ hai, toh $a x + m y = 1$ se coefficient $x$ hi inverse $a^{- 1} (mod m)$ hai.

Linear Diophantine equation

a x + b y = c

ke integer solutions kab hote hain?

Tabhi aur sirf tabhi jab

g cd (a, b)

c

ko divide kare.

Agar $56 x + 15 y = g cd (56, 15)$ hai, toh $x$ aur $y$ kya hain? :: $x = - 4$ , $y = 15$ , kyunki $56 (- 4) + 15 (15) = 1$ aur $g cd (56, 15) = 1$ .

Hum gcd aur coefficients ke liye second-to-last row kyun use karte hain?

Last remainder hamesha 0 hota hai. gcd last non-zero remainder hota hai, jo second-to-last row mein appear hota hai.

Bézout's Identity kya hai?

Kisi bhi integers

a, b

ke liye (jo dono zero na hon), integers

x, y

exist karte hain jaise ki

a x + b y = g cd (a, b)