Bézout Özdeşliği: İki Sayının EBOB'una Giden Lineer Yol

Bir bisikletçi paradoksu

Bir hız antrenörü diyor ki: "30 saniyede bir antrenmanın sona erdiğini bildiren bir düdük çal, ve 42 saniyede bir su molası için başka bir düdük çal. İki düdüğün ilk kez aynı anda çalmasına ne kadar var?"

Cevap $\mathrm{EKOK}(30, 42) = 210$ saniye. Tamam. Ama tersini soralım:

"İki düdük arasındaki en kısa zaman farkı kaç saniye olabilir?"

Cevap 6 saniye — yani $\gcd(30, 42)$. Ve buna ulaşmanın somut yolu vardır: bu, Bézout özdeşliğidir.

Teoremin sade ifadesi

Bézout özdeşliği (veya Bézout lemması) şunu söyler:

Sıfırdan farklı iki tam sayı $a$ ve $b$ verildiğinde, $ax + by = \gcd(a, b)$ denklemini sağlayan tam sayı $x, y$ vardır.

Örnek: $a = 30, b = 42$. EBOB(30, 42) = 6. Bézout der ki, $30x + 42y = 6$ denkleminin tam sayı çözümü vardır. Gerçekten:

$30 \cdot 3 + 42 \cdot (-2) = 90 - 84 = 6 \checkmark$

Yani $x = 3, y = -2$ işe yarıyor. (Ve sonsuz başka çözüm de var.)

Neden "doğal" değil?

Çocukken EBOB'u öğrendiniz: ortak böleni bul. Ama EBOB'un $a$ ve $b$'nin tam sayı katlarının toplamı olarak ifade edilebileceği apaçık değil. Bézout'nun katkısı bu garantidir.

İddianın gücü şurada: $\gcd(a, b)$, $a$ ve $b$'den üretilen $\{ax + by : x, y \in \mathbb{Z}\}$ kümesinin en küçük pozitif elemanıdır.

Bu küme bir ideal oluşturur (modern cebir terimiyle). Ve $\mathbb{Z}$'de her ideal asal ideal = tek bir sayının katlarının kümesi. O sayı işte $\gcd(a, b)$.

Genişletilmiş Öklid algoritması — yapıcı kanıt

Bézout'nun gücü "var" demekle bitmez; $x$ ve $y$'yi açıkça hesaplar. Yöntem genişletilmiş Öklid algoritması:

Önce klasik Öklid algoritması ile EBOB(30, 42) hesaplanır:

• $42 = 30 \cdot 1 + 12$
• $30 = 12 \cdot 2 + 6$
• $12 = 6 \cdot 2 + 0$

EBOB = 6. Şimdi geri yön:

• $6 = 30 - 12 \cdot 2$
• $12 = 42 - 30 \cdot 1$, yerine koy:
• $6 = 30 - (42 - 30) \cdot 2 = 30 \cdot 3 - 42 \cdot 2$

İşte $x = 3, y = -2$. Bu algoritma her zaman çalışır.

Bézout özdeşliğinin sonuçları

1. $\gcd = 1$ ise modüler ters

Eğer $\gcd(a, n) = 1$ ise, Bézout der ki $ax + ny = 1$ çözümü var. Bunu $\bmod n$ alırsak:

$ax \equiv 1 \pmod{n}$

Yani $x$, $a$'nın $\bmod n$ modüler tersidir. Bu, RSA şifrelemenin matematik temelidir: özel anahtar üretirken modüler ters alırız.

2. Doğrusal Diofantos denklemi

$ax + by = c$ denkleminin tam sayı çözümü olması için gerek ve yeter koşul: $\gcd(a, b) \mid c$.

Örnek: $30x + 42y = 100$ çözülemez (çünkü EBOB=6, ve $6 \nmid 100$). Ama $30x + 42y = 12$ çözülür.

3. Aritmetiğin Temel Teoremi'nin kanıtı

"Her tam sayı, asalların tek bir yolla çarpımıdır." Bunu kanıtlamak için Öklid'in lemması gerekir: $p$ asal, $p \mid ab$ ise $p \mid a$ veya $p \mid b$. Öklid'in lemmasının kanıtı doğrudan Bézout özdeşliğine dayanır.

Yani Bézout, modern aritmetiğin asal çarpan ayrışımı dahil temel taşı.

Birden fazla sayı için genelleştirme

Üç sayı $a, b, c$ için de Bézout geçerli:

$ax + by + cz = \gcd(a, b, c)$

ve tam sayı $x, y, z$ vardır. Genelde $n$ sayı için:

$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = \gcd(a_1, \ldots, a_n)$

İspat: $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$ özyinelemesi.

Polinomlarda Bézout

Bézout özdeşliği polinomlara da genişler. İki polinom $f(x)$ ve $g(x)$ (bir cisim üzerinde) için:

$A(x) f(x) + B(x) g(x) = \gcd(f, g)$

ve polinom $A, B$ vardır. Bu, lineer cebirin temellerinden ve kodlama teorisinden (Reed-Solomon kodları) modern kriptografiye kadar pek çok yerde kullanılır.

Étienne Bézout kimdi?

Étienne Bézout (1730-1783), Fransız matematikçi. Cebir kitabı yazarı. Asıl ünü iki başka teoremden gelir:

1. Polinom Bézout teoremi (1779): $n$ ve $m$ dereceli iki cebrik eğri (komplex projektif düzlemde) tam $nm$ noktada kesişir (çokluk dahil).
2. Bézout matrisi: rezultant hesabı için.

İlginç olan: bizim "Bézout özdeşliği" dediğimiz teorem aslında Bézout'tan önce biliniyordu — Claude Gaspard Bachet 1624'te yayımladı, Öklid'in algoritmasından beri kanıt yapılır olmuştu. Ama Fransız akademik gelenek bu özdeşliği Bézout'nun adıyla anar. Tarih böyle haksızlıklarla dolu.

Pratik bir bulmaca

"Bir terazide 3 ve 5 kg'lık iki tartı var. Bu iki tartıyı kullanarak hangi ağırlıkları tam olarak ölçebilirsiniz?"

Bézout: $\gcd(3, 5) = 1$. Yani her tam sayı kg'ı ölçebilirsiniz. Örneğin 1 kg: $3 \cdot 2 - 5 \cdot 1 = 1$. Yani sol kefeye 2 adet 3 kg, sağ kefeye 1 adet 5 kg + ölçülecek nesne → denge.

Bu bulmaca doğrudan Bézout'tur. Üç bin yıl boyunca terazi ustaları bilmeden bu teoremi uyguladılar.

Sonuç

Bézout özdeşliği, "iki sayının EBOB'u lineer olarak ifade edilebilir" der. Bu masum cümlenin sonuçları:

• Modüler ters → RSA şifreleme.
• Aritmetiğin Temel Teoremi'nin ispatı.
• Diofantos denklemleri çözülebilirlik kriteri.
• Polinomlarda EBOB ve kod çözme.

Sayı teorisinin görünmez kahramanı. Adı bile yanlış yere yapışmış olsa, etkisi her gün milyarlarca şifreli mesajda yaşıyor.