Bézout's identity

2.5.9 · Maths › Number Theory (Intermediate)

Bézout's Identity Kya Hai?

Yeh kyun important hai?

Yeh prove karta hai ki GCD ko ek integer linear combination ke roop mein express kiya ja sakta hai
Yeh Extended Euclidean Algorithm ki neenv hai
Iska use linear Diophantine equations solve karne mein hota hai
Yeh dikhata hai ki GCD "sabse chhota positive" linear combination kyun hota hai

Derivation: Pehle Principles Se

Chalo Bézout's Identity ko scratch se prove karte hain.

Step 1: Saari linear combinations ka set define karo

Let $S = {a x + b y : x, y \in Z, a x + b y > 0}$

Yeh un saare positive integers ka set hai jo hum $a$ aur $b$ ko combine karke bana sakte hain.

Yeh set kyun? Hum $a x + b y$ ke roop mein expressible sabse chhota positive number dhundhna chahte hain. Hum dikhayenge ki yeh sabse chhota number hi GCD hota hai.

Step 2: Dikhao ki $S$ non-empty hai

Kyunki $a$ aur $b$ dono ek saath zero nahi hain, hum aisi combinations choose kar sakte hain jo positive hon:

Agar $a > 0$ hai: $x = 1, y = 0$ choose karo, jisse $a \in S$ milta hai
Agar $a < 0$ hai: $x = - 1, y = 0$ choose karo, jisse $- a = ∣ a ∣ \in S$ milta hai

Toh $S$ mein kam se kam $∣ a ∣$ ya $∣ b ∣$ zaroor hai. ✓

Step 3: $d$ ko $S$ ka sabse chhota element maano

Well-Ordering Principle ke according, $S$ mein ek sabse chhota element hoga. Use $d$ kehte hain.

Kyunki $d \in S$ hai, hum likh sakte hain: $d = a x_{0} + b y_{0}$ kuch integers $x_{0}, y_{0}$ ke liye.

Step 4: Prove karo ki $d$ doono $a$ aur $b$ ko divide karta hai

Claim: $d ∣ a$

Contradiction se proof: $a$ aur $d$ par Division Algorithm apply karo: $a = q d + r where 0 \leq r < d$

$d = a x_{0} + b y_{0}$ substitute karo: $a = q (a x_{0} + b y_{0}) + r$ $r = a - q (a x_{0} + b y_{0}) = a (1 - q x_{0}) + b (- q y_{0})$

Yeh step kyun? Humne $r$ ko $a$ aur $b$ ki linear combination ke roop mein express kar diya.

Agar $r > 0$ hota, toh $r \in S$ hota (yeh ek positive linear combination hai). Lekin $r < d$ hai, jo is fact se contradict karta hai ki $d$ , $S$ ka sabse chhota element hai.

Isliye $r = 0$ hai, toh $d ∣ a$ . ✓

Bilkul usi reasoning se, $d ∣ b$ . ✓

Step 5: Prove karo ki $d$ hi GCD hai

Humne dikhaya ki $d$ , $a$ aur $b$ ka ek common divisor hai.

Ab maano $c$ koi bhi common divisor ho $a$ aur $b$ ka. Toh:

$c ∣ a ⟹ a = c m$ kisi integer $m$ ke liye
$c ∣ b ⟹ b = c n$ kisi integer $n$ ke liye

Isliye: $d = a x_{0} + b y_{0} = c m x_{0} + c n y_{0} = c (m x_{0} + n y_{0})$

Toh $c ∣ d$ .

Yeh kyun important hai: Koi bhi common divisor $d$ ko divide karta hai, isliye $d$ greatest common divisor hai.

Iss prakar $d = g cd (a, b)$ aur humhare paas hai: $g cd (a, b) = a x_{0} + b y_{0}$

Isse proof complete hota hai. □

Bézout Coefficients Dhundhna: Extended Euclidean Algorithm

Back-Substitution Method

Worked example Example 1:

$a = 240, b = 46$ ke liye Bézout coefficients dhundho

Step 1: Euclidean Algorithm chalao

240 &= 46 \cdot 5 + 10\\ 46 &= 10 \cdot 4 + 6 \\ 10 &= 6 \cdot 1 + 4 \\ 6 &= 4 \cdot 1 + 2 \\ 4 &= 2 \cdot 2 + 0 \end{align}$$ Toh $\gcd(240, 46) = 2$. **Step 2: 2 ko express karne ke liye back-substitute karo** Doosri-se-aakhiri equation se shuru karo: $$2 = 6 - 4 \cdot 1$$ **Yeh step kyun?** Hum remainder 2 ko isolate karte hain. Pichhli equation se $4$ express karo: $$4 = 10 - 6 \cdot 1$$ Substitute karo: $$2 = 6 - (10 - 6 \cdot 1) \cdot 1 = 6 - 10 + 6 = 2\cdot 6 - 10$$ Pehle se $6$ express karo: $$6 = 46 - 10 \cdot 4$$ Substitute karo: $$2 = 2(46 - 10 \cdot 4) - 10 = 2 \cdot 46 - 8 \cdot 10 - 10 = 2 \cdot 46 - 9 \cdot 10$$ Pehli equation se $10$ express karo: $$10 = 240 - 46 \cdot 5$$ Substitute karo: $$2 = 2 \cdot 46 - 9(240 - 46 \cdot 5) = 2 \cdot 46 - 9 \cdot 240 + 45 \cdot 46$$ $$2 = 47 \cdot 46 - 9 \cdot 240$$ Rearrange karne par: $$2 = 240 \cdot (-9) + 46 \cdot 47$$ **Answer:** $x = -9, y = 47$ **Verify karo:** $240(-9) + 46(47) = -2160 + 2162 = 2$ ✓

Bézout Coefficients Ki Non-Uniqueness

Kyun? Maano $d = g cd (a, b)$ . $a x_{0} + b y_{0} = d$ se shuru karke:

$a (x_{0} + k \cdot \frac{b}{d}) + b (y_{0} - k \cdot \frac{a}{d}) = a x_{0} + b y_{0} + ak \frac{b}{d} - bk \frac{a}{d} = d + 0 = d$

Extra terms cancel ho jaate hain! Isse infinitely many coefficient pairs milte hain.

Applications

1. Linear Diophantine Equations Solve Karna

Equation $a x + b y = c$ ke integer solutions tab aur sirf tab hote hain jab $g cd (a, b) ∣ c$ ho.

Agar $a x_{0} + b y_{0} = g cd (a, b)$ hai, toh $\frac{c}{g c d ( a , b )}$ se multiply karo ek solution paane ke liye.

2. Modular Inverses

Agar $g cd (a, m) = 1$ hai, toh $a x + m y = 1$ ke solutions hote hain. Iska matlab hai $a x \equiv 1 (mod m)$ , toh $x$ , $a$ ka modulo $m$ multiplicative inverse hai.

3. Coprimality Proof

Bézout's Identity coprimality ki ek alternative characterization deta hai: $g cd (a, b) = 1 ⟺ \exists x, y \in Z : a x + b y = 1$

Active Recall Flashcards

#flashcards/maths

Bézout's Identity kya kehta hai? :: Kisi bhi integers $a$ aur $b$ ke liye (dono ek saath zero nahi), kuch integers $x$ aur $y$ exist karte hain jaise ki $a x + b y = g cd (a, b)$ .

Bézout coefficients kya hote hain?

Equation

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

mein integers

x

aur

y

ko Bézout coefficients kehte hain.

Bézout coefficients kaise dhundhe jaate hain?

Extended Euclidean Algorithm use karo: Euclidean algorithm chalao, phir GCD ko linear combination ke roop mein express karne ke liye remainders ko back-substitute karo.

Agar

(x_{0}, y_{0})

a x + b y = d

ka ek solution hai, toh general solution kya hai?

x = x_{0} + k (b / d)

aur

y = y_{0} - k (a / d)

kisi bhi integer

k

ke liye, jahaan

d = g cd (a, b)

hai.

True ya false: Bézout's Identity sirf tab apply hota hai jab

g cd (a, b) = 1

ho.

False. Yeh kisi bhi integers

a, b

par apply hota hai jab dono ek saath zero na hon, chahe unka GCD kuch bhi ho.

Bézout's Identity prove karne mein key insight kya hai? :: Set $S$ ko consider karo jo saare positive linear combinations $a x + b y$ ka hota hai. $S$ ka sabse chhota element GCD hota hai, Well-Ordering Principle aur divisibility arguments ke zariye.

a x + b y = c

ke integer solutions kab hote hain?

Tab aur sirf tab jab

g cd (a, b)

c

ko divide kare.

Modular inverses dhundhne mein Bézout's Identity ka use kaise hota hai?

Agar

g cd (a, m) = 1

hai, toh

a x + m y = 1

solve karne se

x

milta hai jaise ki

a x \equiv 1 (mod m)

, toh

x

a

ka modular inverse hai.

Recall Ek 12-saal ke bacche ko samjhao

Socho tumhare paas do tarah ke coins hain: ek 35 cents ka aur ek 15 cents ka. Kya tum sirf inhi coins se exactly 5 cents bana sakte ho? Tumhe shayad kuch coins "wapas dene" padenge (negative coefficients).

Bézout's Identity kehta hai: agar tumhare paas do numbers $a$ aur $b$ hain, toh tum unke sahi multiples ko jod-ghatakar hamesha unka GCD bana sakte ho. Yeh ek magic recipe ki tarah hai: "Pehle number ke $x$ lo, doosre ke $y$ lo (kuch negative bhi ho sakte hain, matlab subtract karo), aur tumhe exactly unka GCD milega."

Yeh cool kyun hai? Kyunki iska matlab hai ki GCD sirf koi abstract "sabse bada common divisor" nahi hai—yeh kuch aisa hai jo tum original numbers se bana sakte ho. Aur Extended Euclidean Algorithm ek step-by-step recipe hai jo exactly batata hai ki tumhe kitne ek-ek number chahiye.

Connections

Euclidean Algorithm — Bézout coefficients is algorithm ko extend karke milte hain
Extended Euclidean Algorithm — $x$ aur $y$ dhundhne ka computational method
Linear Diophantine Equations — Bézout's Identity solvability determine karta hai
Modular Arithmetic — Modular inverses compute karne mein use hota hai
Greatest Common Divisor — Bézout's Identity ek alternative characterization deta hai
Coprime Integers — Special case jab $g cd (a, b) = 1$ ho