4 En Büyük Ortak Bölen ve Bézout Teoremi
İki tam sayının ortak bölenleri, aralarındaki çarpımsal akrabalığın ölçüsüdür. Bu bölümde bu akrabalığı tek bir sayıyla — en büyük ortak bölenle — özetleyecek ve bu sayının şaşırtıcı bir başka yüzü olduğunu göreceğiz: en büyük ortak bölen, aynı zamanda iki sayının doğrusal birleşimi olarak yazılabilen en küçük pozitif tam sayıdır. Bu ikinci yüz, Bézout teoreminin içeriğidir ve dersin geri kalanının motorudur.
4.1 Ortak Bölenler
Tanım 4.1 (Ortak Bölen) \(a, b\) ve \(d\) birer tam sayı olsun. Eğer \(d \mid a\) ve \(d \mid b\) ise \(d\) tam sayısına \(a\) ile \(b\)’nin bir ortak böleni denir.
Örnek 4.1 (Ortak Bölen Örneği) \(4\) tam sayısı \(12\) ile \(20\)’nin bir ortak bölenidir; çünkü \(4 \mid 12\) ve \(4 \mid 20\)’dir.
Buna karşılık \(5\) sayısı \(20\) ile \(12\)’nin bir ortak böleni değildir: \(5 \mid 20\) olsa da \(5 \nmid 12\)’dir.
Her \(a, b\) çifti için \(1\) sayısı bir ortak bölendir; dolayısıyla ortak bölenler kümesi hiçbir zaman boş değildir. Asıl soru bu kümenin en büyük elemanıdır.
Tanım 4.2 (En Büyük Ortak Bölen) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olmak üzere, hem \(a\)’yı hem de \(b\)’yi bölen tam sayıların en büyüğüne \(a\) ile \(b\)’nin en büyük ortak böleni denir ve
\[\gcd(a, b)\]
ile gösterilir.
1. Neden \(a\) ile \(b\)’nin ikisi birden sıfır olamıyor?
Her tam sayı \(0\)’ı böldüğünden (\(\thinspace\)Teorem 3.1 (2)\(\thinspace\)), \(a = b = 0\) alınırsa her tam sayı bir ortak bölen olur. Bu küme üstten sınırlı değildir; en büyük elemanı yoktur. Bu yüzden \(\gcd(0,0)\) tanımsız bırakılır.
2. En büyük ortak bölen gerçekten var mıdır?
Vardır. \(a\) ile \(b\)’nin ortak bölenlerinin kümesine \(D\) diyelim.
- \(1 \in D\) olduğundan \(D \neq \emptyset\)’dır.
- \(a\) ile \(b\)’den en az biri, diyelim \(a\), sıfırdan farklıdır. Her \(d \in D\) için \(d \mid a\) ve \(a \neq 0\) olduğundan Teorem 3.1 (8) gereği \(|d| \leq |a|\)’dır; yani \(D\) kümesi \(|a|\) ile üstten sınırlıdır.
Boş olmayan ve üstten sınırlı bir tam sayı kümesinin en büyük elemanı vardır. O hâlde \(\gcd(a,b)\) iyi tanımlıdır. Ayrıca \(1 \in D\) olduğundan daima \(\gcd(a,b) \geq 1 > 0\)’dır.
Tanımı doğrudan kullanan bir ölçüt, ilerideki ispatlarda işimizi kolaylaştıracaktır.
Önerme 4.1 (EBOB’un Sıralamayla Karakterizasyonu) \(a\) ile \(b\) ikisi birden sıfır olmayan tam sayılar ve \(d \in \mathbb{Z}\) olsun. \(d = \gcd(a,b)\) olabilmesi için gerek ve yeter koşullar şunlardır:
- \(d \mid a\) ve \(d \mid b\);
- her \(c \in \mathbb{Z}\) için, \(c \mid a\) ve \(c \mid b\) ise \(c \leq d\)’dir.
Bu ölçüt tanımın yeniden ifade edilmiş hâlidir: birinci madde \(d\)’nin bir ortak bölen olduğunu, ikincisi de ortak bölenlerin en büyüğü olduğunu söyler.
4.2 Bézout Teoremi
Şimdi bu bölümün — hatta dersin — en önemli teoremine geliyoruz. Teorem, en büyük ortak böleni yepyeni bir biçimde tanımlar: \(a\) ile \(b\)’nin katlarının toplamı olarak yazılabilen en küçük pozitif sayı.
Teorem 4.1 (Bézout Teoremi) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olsun. Bu durumda
\[\gcd(a, b) = a x_0 + b y_0\]
olacak biçimde \(x_0, y_0\) tam sayıları vardır.
İspat
Aşağıdaki kümeyi tanımlayalım:
\[S = \{ ax + by \ : \ x, y \in \mathbb{Z}, \ ax + by > 0 \}\]
1. \(S\) boş değildir. \(x = a\), \(y = b\) seçelim:
\[a \cdot a + b \cdot b = a^2 + b^2 > 0\]
(Toplam sıfır olamaz, çünkü \(a\) ile \(b\)’nin ikisi birden sıfır değildir.) O hâlde \(a^2 + b^2 \in S\)’dir ve \(S\) boş kümeden farklı bir doğal sayı kümesidir.
2. \(S\)’nin en küçük elemanı bir ortak bölendir. İyi sıralama prensibine göre \(S\) kümesinin bir en küçük elemanı vardır; buna \(d\) diyelim. \(d \in S\) olduğundan
\[d = a x_1 + b y_1\]
olacak biçimde \(x_1, y_1\) tam sayıları vardır.
İddia. \(d \mid a\)’dır.
İddianın ispatı. Bölme algoritmasına göre
\[a = dq + r, \qquad 0 \leq r < d\]
olacak biçimde \(q, r\) tam sayıları vardır. \(d \nmid a\) olduğunu varsayalım; bu durumda \(r \neq 0\), yani \(0 < r < d\)’dir. Şimdi \(r\)’yi \(a\) ile \(b\) cinsinden yazalım:
\[ \begin{aligned} r &= a - dq \\ &= a - (a x_1 + b y_1)q \\ &= a(1 - x_1 q) + b(-y_1 q) \end{aligned} \]
Görüldüğü gibi \(r\) sayısı \(a\) ile \(b\)’nin bir doğrusal birleşimidir ve \(r > 0\)’dır; yani \(r \in S\)’dir. Ama \(r < d\) olması, \(d\)’nin \(S\)’nin en küçük elemanı olmasıyla çelişir. O hâlde \(r = 0\), yani \(d \mid a\) olmalıdır.
Tamamen benzer biçimde \(d \mid b\) olduğu da gösterilir. Demek ki \(d\) sayısı \(a\) ile \(b\)’nin bir ortak bölenidir. En büyük ortak bölen, ortak bölenlerin en büyüğü olduğundan
\[d \leq \gcd(a,b) \tag{1}\]
yazılır.
3. Ters eşitsizlik. \(\gcd(a,b) \mid a\) ve \(\gcd(a,b) \mid b\) olduğundan, Teorem 3.1 (6) gereği \(\gcd(a,b)\) sayısı \(a\) ile \(b\)’nin her doğrusal birleşimini böler; özel olarak
\[\gcd(a,b) \ \mid \ a x_1 + b y_1 = d\]
olur. \(d > 0\) olduğundan Teorem 3.1 (8) gereği
\[\gcd(a,b) \leq d \tag{2}\]
bulunur.
\((1)\) ve \((2)\) birlikte \(d = \gcd(a,b)\) verir; yani \(\gcd(a,b) = a x_1 + b y_1\)’dir.
\(\blacksquare\)
İspatın kendisi, teoremden daha fazlasını söyler; bu ek bilgiyi ayrıca kaydedelim.
Sonuç 4.1 (EBOB, En Küçük Pozitif Doğrusal Birleşimdir) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olsun. Bu durumda \(a\) ile \(b\)’nin en büyük ortak böleni,
\[S = \{ ax + by \ : \ x, y \in \mathbb{Z}, \ ax + by > 0 \}\]
kümesinin en küçük elemanıdır:
\[\gcd(a, b) = \min S = \min \{ ax + by \ : \ x, y \in \mathbb{Z}, \ ax + by > 0 \}\]
Teorem \(x_0\) ile \(y_0\)’ın var olduğunu söyler, tek olduğunu değil. Nitekim
\[\gcd(a,b) = a x_0 + b y_0 = a(x_0 + b) + b(y_0 - a)\]
eşitliği gösteriyor ki katsayılar sonsuz çok biçimde seçilebilir. Örneğin
\[\gcd(4, 6) = 2 = 4 \cdot (-1) + 6 \cdot 1 = 4 \cdot 2 + 6 \cdot (-1)\]
Bu esneklik bir kusur değil, avantajdır: ileride Diofant denklemlerinin sonsuz çözümünü tam olarak bu serbestlik üretecektir.
4.3 Doğrusal Birleşimlerin Kümesi
Bézout teoremi en küçük pozitif doğrusal birleşimi tanır. Bir sonraki sonuç, bütün doğrusal birleşimlerin ne olduğunu söyler.
Sonuç 4.2 (Doğrusal Birleşimler Kümesi) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olsun ve \(d = \gcd(a,b)\) biçiminde tanımlansın. Bu durumda
\[T = \{ ax + by \ : \ x, y \in \mathbb{Z} \}\]
kümesi, \(d\)’nin tüm katlarının kümesidir:
\[T = \{ dk \ : \ k \in \mathbb{Z} \}\]
İspat
İki kapsamayı ayrı ayrı gösterelim.
\(T \subseteq \{dk\}\). \(ax + by \in T\) olsun. \(d \mid a\) ve \(d \mid b\) olduğundan Teorem 3.1 (6) gereği \(d \mid ax + by\)’dir; yani \(ax + by\) sayısı \(d\)’nin bir katıdır.
\(\{dk\} \subseteq T\). Bézout teoremi gereği \(d = a x_0 + b y_0\) olacak biçimde \(x_0, y_0\) tam sayıları vardır. Herhangi bir \(k \in \mathbb{Z}\) için her iki tarafı \(k\) ile çarpalım:
\[dk = a(x_0 k) + b(y_0 k)\]
\(x_0 k\) ve \(y_0 k\) tam sayı olduğundan \(dk \in T\)’dir.
İki kapsama birlikte \(T = \{dk : k \in \mathbb{Z}\}\) verir.
\(\blacksquare\)
Bu sonuç, “\(ax + by = c\) denkleminin tam sayı çözümü var mıdır?” sorusuna tek satırda cevap verir: çözüm vardır ancak ve ancak \(\gcd(a,b) \mid c\) ise. Diofant denklemleri bölümünde bu ölçütü doğrudan kullanacağız.
Aşağıdaki karakterizasyon, en büyük ortak böleni “en büyük” sıfatından kurtarır: ortak bölenlerin yalnızca daha küçük değil, aynı zamanda \(d\)’yi bölen sayılar olduğunu söyler. Bu, ileride sıralamanın anlamsız olduğu ortamlarda da kullanılabilecek olan asıl tanımdır.
Teorem 4.2 (EBOB’un Bölünebilmeyle Karakterizasyonu) \(a, b, d \in \mathbb{Z}\), \(a\) ile \(b\) ikisi birden sıfır değil ve \(d > 0\) olsun. \(d = \gcd(a,b)\) olabilmesi için gerek ve yeter koşullar şunlardır:
- \(d \mid a\) ve \(d \mid b\);
- her \(c \in \mathbb{Z}\) için, \(c \mid a\) ve \(c \mid b\) ise \(c \mid d\)’dir.
İspat
(\(\Rightarrow\)) \(d = \gcd(a,b)\) olsun. Birinci koşul en büyük ortak bölenin tanımı gereği sağlanır.
İkinci koşul için \(c \mid a\) ve \(c \mid b\) olsun. Bézout teoremi gereği \(d = a x_0 + b y_0\) yazılabilir. Teorem 3.1 (6) gereği \(c\) sayısı bu doğrusal birleşimi böler:
\[c \mid a x_0 + b y_0 = d\]
(\(\Leftarrow\)) \(d > 0\) olsun ve iki koşulu sağlasın. Birinci koşul gereği \(d\) bir ortak bölendir. Şimdi \(c\) herhangi bir ortak bölen olsun. İkinci koşul gereği \(c \mid d\)’dir ve \(d > 0\) olduğundan Teorem 3.1 (8) gereği
\[c \leq |c| \leq |d| = d\]
bulunur. Yani \(d\), ortak bölenlerin en büyüğüdür: \(d = \gcd(a,b)\).
\(\blacksquare\)
4.4 EBOB’un Temel Özellikleri
Önerme 4.2 (EBOB’un Temel Özellikleri) Aşağıdakiler geçerlidir.
Her \(a \neq 0\) için \(\gcd(a, 0) = |a|\).
\(a \neq 0\) ve \(a \mid b\) ise \(\gcd(a, b) = |a|\).
İkisi birden sıfır olmayan her \(a, b\) için
\[\gcd(a,b) = \gcd(-a, b) = \gcd(a, -b) = \gcd(-a, -b)\]
İkisi birden sıfır olmayan her \(a, b\) ve her \(0 < m \in \mathbb{Z}\) için
\[\gcd(ma, mb) = m \cdot \gcd(a, b)\]
İspat
(1) Her tam sayı \(0\)’ı böldüğünden, \(a\) ile \(0\)’ın ortak bölenleri tam olarak \(a\)’nın bölenleridir. \(a \neq 0\) olduğundan bunların en büyüğü \(|a|\)’dır: \(|a| \mid a\) olduğu açıktır ve Teorem 3.1 (8) gereği \(a\)’nın her böleni mutlak değerce \(|a|\)’yı geçemez.
(2) \(a \mid b\) olsun. \(a\) ile \(b\)’nin ortak bölenlerini belirleyelim. \(|a|\) sayısı hem \(a\)’yı hem de (geçişme gereği) \(b\)’yi böler; yani bir ortak bölendir. Öte yandan her ortak bölen \(a\)’yı böldüğünden mutlak değerce \(|a|\)’yı geçemez. O hâlde \(\gcd(a,b) = |a|\)’dır.
(3) Teorem 3.1 (13) gereği \(c \mid a\) ile \(c \mid -a\) önermeleri denktir. Dolayısıyla \(\{a, b\}\) çiftinin ortak bölenleri ile \(\{-a, b\}\), \(\{a, -b\}\), \(\{-a, -b\}\) çiftlerinin ortak bölenleri aynı kümedir. Aynı kümenin en büyük elemanı da aynı olacağından dört en büyük ortak bölen eşittir.
(4) Sonuç 4.1 gereği en büyük ortak bölen, pozitif doğrusal birleşimlerin en küçüğüdür. \(m > 0\) olduğundan
\[ \begin{aligned} \gcd(ma, mb) &= \min \{ (ma)x + (mb)y \ : \ x,y \in \mathbb{Z}, \ (ma)x + (mb)y > 0 \} \\ &= \min \{ m(ax + by) \ : \ x,y \in \mathbb{Z}, \ ax + by > 0 \} \\ &= m \cdot \min \{ ax + by \ : \ x,y \in \mathbb{Z}, \ ax + by > 0 \} \\ &= m \cdot \gcd(a,b) \end{aligned} \]
Üçüncü satırda \(m > 0\) olmasını kullandık: pozitif bir sayıyla çarpmak sıralamayı bozmaz, dolayısıyla minimumu dışarı alabiliriz.
\(\blacksquare\)
4.5 Aralarında Asal Sayılar
En büyük ortak bölenin alabileceği en küçük değer \(1\)’dir. Bu durum o kadar sık karşımıza çıkar ki kendi adını hak eder.
Tanım 4.3 (Aralarında Asal Sayılar) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olsun. Ancak ve yalnız
\[\gcd(a,b) = 1\]
olması durumunda “\(a\) ile \(b\) aralarında asaldır” denir.
Bézout teoreminin en çok kullanılan biçimi, aralarında asallık için verdiği pratik ölçüttür.
Sonuç 4.3 (Aralarında Asallık Ölçütü) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olsun. \(a\) ile \(b\)’nin aralarında asal olması için gerek ve yeter koşul
\[1 = ax + by\]
olacak biçimde \(x, y\) tam sayılarının var olmasıdır.
İspat
(\(\Rightarrow\)) \(\gcd(a,b) = 1\) olsun. Bézout teoremi gereği \(\gcd(a,b) = ax_0 + by_0\) olacak biçimde \(x_0, y_0\) tam sayıları vardır; yani \(1 = a x_0 + b y_0\)’dır.
(\(\Leftarrow\)) \(1 = ax + by\) olacak biçimde \(x, y\) tam sayıları bulunsun. \(d = \gcd(a,b)\) diyelim. \(d \mid a\) ve \(d \mid b\) olduğundan Teorem 3.1 (6) gereği
\[d \mid ax + by = 1\]
olur. \(d\) pozitif bir tam sayı ve \(d \mid 1\) olduğundan \(d = 1\)’dir.
\(\blacksquare\)
İki sayının aralarında asal olduğunu göstermek için artık bütün ortak bölenleri incelemek gerekmez: değeri \(1\) olan tek bir doğrusal birleşim bulmak yeterlidir. Aşağıdaki örneklerin çoğu bu tek satırlık numaraya dayanır.
Dikkat: ölçüt yalnızca \(1\) değeri için bu kadar keskindir. \(ax + by = 6\) biçiminde bir birleşim bulmak \(\gcd(a,b) = 6\) olduğunu göstermez; yalnızca \(\gcd(a,b) \mid 6\) olduğunu söyler.
4.6 Çözümlü Örnekler
Örnek 4.2 (Ardışık Sayılar Aralarında Asaldır) Her \(n\) tam sayısı için \(\gcd(n, n+1) = 1\) olduğunu gösteriniz.
Çözüm
1. Yol (Bézout ölçütü). Aşağıdaki doğrusal birleşimi yazalım:
\[(n+1) \cdot 1 + n \cdot (-1) = 1\]
Sonuç 4.3 gereği \(\gcd(n, n+1) = 1\)’dir.
2. Yol (doğrudan). \(d = \gcd(n, n+1)\) olsun. O hâlde \(d \mid n\) ve \(d \mid n+1\)’dir. Teorem 3.1 (7) gereği \(d\) sayısı farkı da böler:
\[d \mid (n+1) - n = 1\]
\(d\) pozitif olduğundan \(d = 1\)’dir.
\(\blacksquare\)
Örnek 4.3 (\(\gcd(a, a+n)\) Sayısı \(n\)’yi Böler) İkisi birden sıfır olmayan her \(n, a\) tam sayısı için \(\gcd(a, a+n)\) sayısının \(n\)’yi böldüğünü gösteriniz.
Çözüm
\(d = \gcd(a, a+n)\) biçiminde tanımlansın. En büyük ortak bölenin tanımı gereği
\[d \mid a \qquad \text{ve} \qquad d \mid a + n\]
olur. Teorem 3.1 (7) gereği \(d\) sayısı bu ikisinin farkını da böler:
\[d \mid (a + n) - a = n\]
O hâlde \(\gcd(a, a+n) \mid n\)’dir.
\(\blacksquare\)
Örnek 4.4 (Hangi Değerler Ortaya Çıkar?) \(n\) sıfırdan farklı bir tam sayı olmak üzere
\[\{ \gcd(a, a+n) \ : \ a \in \mathbb{Z} \} = \{ k \in \mathbb{Z} \ : \ 0 < k, \ k \mid n \}\]
olduğunu gösteriniz.
Çözüm
Kümeleri kısaca adlandıralım:
\[A := \{ \gcd(a, a+n) : a \in \mathbb{Z} \}, \qquad B := \{ k \in \mathbb{Z} : 0 < k, \ k \mid n \}\]
\(A \subseteq B\). \(d \in A\) olsun; yani \(d = \gcd(a, a+n)\) olacak biçimde bir \(a \in \mathbb{Z}\) vardır. Örnek 4.3 gereği \(d \mid n\)’dir. Ayrıca en büyük ortak bölen daima pozitiftir. O hâlde \(d \in B\)’dir.
\(B \subseteq A\). \(k \in B\) olsun; yani \(0 < k\) ve \(k \mid n\)’dir. Şimdi \(a = k\) seçelim ve \(\gcd(k, k+n) = k\) olduğunu gösterelim:
- \(k \mid k\) olduğu açıktır.
- \(k \mid n\) olduğundan Teorem 3.1 (7) gereği \(k \mid k + n\)’dir.
Demek ki \(k\), \(\{k, k+n\}\) çiftinin bir ortak bölenidir. Öte yandan her ortak bölen \(k\)’yı böldüğünden mutlak değerce \(k\)’yı geçemez. O hâlde
\[\gcd(k, k+n) = k\]
olur ve \(k \in A\)’dır.
İki kapsama birlikte \(A = B\) verir.
\(\blacksquare\)
Örnek 4.5 (Doğrusal İfadelerin Aralarında Asallığı) Her \(a\) tam sayısı için \(\gcd(2a+1,\ 9a+4) = 1\) olduğunu gösteriniz.
Çözüm
Sonuç 4.3 gereği, değeri \(1\) olan bir doğrusal birleşim bulmamız yeterlidir. Katsayıları \(a\) terimini yok edecek biçimde seçelim: \(2a+1\) ifadesini \(9\) ile, \(9a+4\) ifadesini \(2\) ile çarparsak her ikisinde de \(18a\) elde ederiz.
\[ \begin{aligned} (2a+1) \cdot 9 + (9a+4) \cdot (-2) &= 18a + 9 - 18a - 8 \\ &= 1 \end{aligned} \]
Değeri \(1\) olan bir doğrusal birleşim bulduğumuz için \(\gcd(2a+1,\ 9a+4) = 1\)’dir.
\(\blacksquare\)
Örnek 4.6 (Tek Sayılarda Bir EBOB Hesabı) Her \(a\) tek tam sayısı için \(\gcd(7a,\ 7a+2) = 1\) olduğunu gösteriniz.
Çözüm
\(d := \gcd(7a,\ 7a+2)\) biçiminde tanımlansın. O hâlde \(d \mid 7a\) ve \(d \mid 7a+2\)’dir; farkı da böler:
\[d \mid (7a + 2) - 7a = 2\]
\(d\) pozitif olduğundan \(d \in \{1, 2\}\)’dir. Şimdi \(d = 2\) olasılığını eleyelim.
\(a\) tek bir tam sayı olduğundan \(7a\) da tektir (tek sayıların çarpımı tektir). Dolayısıyla \(2 \nmid 7a\)’dır. Oysa \(d = 2\) olsaydı \(d \mid 7a\), yani \(2 \mid 7a\) olurdu — çelişki.
O hâlde \(d \neq 2\) ve sonuç olarak
\[\gcd(7a,\ 7a+2) = d = 1\]
bulunur.
\(\blacksquare\)
Örnek 4.7 (Bézout Katsayıları Aralarında Asaldır) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar, \(x, y \in \mathbb{Z}\) ve
\[\gcd(a,b) = ax + by\]
olsun. Bu durumda \(\gcd(x, y) = 1\) olduğunu gösteriniz.
Çözüm
\(d := \gcd(a,b)\) biçiminde tanımlansın. Buradaki kilit fikir, \(a\) ile \(b\)’yi \(d\)’nin katları olarak yazıp eşitliği sadeleştirmektir.
\(d \mid a\) ve \(d \mid b\) olduğundan
\[a = d a', \qquad b = d b'\]
olacak biçimde \(a', b'\) tam sayıları vardır. Bunları hipotezde yerine koyalım:
\[d = ax + by = (d a')x + (d b')y = d\,\big( a'x + b'y \big)\]
\(a\) ile \(b\)’nin ikisi birden sıfır olmadığından \(d \neq 0\)’dır; her iki tarafı \(d\)’ye sadeleştirebiliriz:
\[1 = a'x + b'y\]
Şimdi \(k := \gcd(x,y)\) diyelim. \(k \mid x\) ve \(k \mid y\) olduğundan Teorem 3.1 (6) gereği \(k\) sayısı \(x\) ile \(y\)’nin her doğrusal birleşimini böler; özel olarak
\[k \ \mid \ a'x + b'y = 1\]
\(k\) pozitif bir tam sayı ve \(k \mid 1\) olduğundan \(k = 1\), yani \(\gcd(x,y) = 1\)’dir.
\(\blacksquare\)
4.7 Çalışma Problemleri
Alıştırma 4.1 (EBOB Hesapları) Aşağıdaki en büyük ortak bölenleri bulunuz ve her biri için değeri EBOB’a eşit olan bir doğrusal birleşim yazınız.
a) \(\gcd(12, 18)\) b) \(\gcd(-15, 25)\) c) \(\gcd(17, 0)\) d) \(\gcd(24, 36)\)
Alıştırma 4.2 (Toplam ve Farkın EBOB’u) İkisi birden sıfır olmayan \(a, b\) tam sayıları için \(\gcd(a,b) = 1\) olsun. Bu durumda
\[\gcd(a+b,\ a-b) \in \{1, 2\}\]
olduğunu gösteriniz.
İpucu: \(d = \gcd(a+b, a-b)\) diyerek \(d \mid 2a\) ve \(d \mid 2b\) olduğunu gösteriniz, ardından Önerme 4.2 (4)’ü kullanınız.
Alıştırma 4.3 (Bir Doğrusal Birleşim Kurma) Her \(a\) tam sayısı için
\[1 = a(5x + 7y) + 2x + 3y\]
olacak biçimde \(x, y\) tam sayılarının var olduğunu gösteriniz.
İpucu: Önce \(\gcd(5a+2,\ 7a+3) = 1\) olduğunu gösterip Sonuç 4.3’ü uygulayınız, sonra elde ettiğiniz birleşimi düzenleyiniz.
Alıştırma 4.4 (Çapraz Çarpımların Farkı) \(a, b, c, d \in \mathbb{Z} \setminus \{0\}\) olsun. Eğer
\[ac - bd \in \{1, -1\}\]
ise \(\gcd(a+b,\ c+d) = 1\) olduğunu gösteriniz.
İpucu: \(k = \gcd(a+b, c+d)\) diyerek \(k \mid c(a+b) - b(c+d)\) hesabını yapınız.
Alıştırma 4.5 (Üç Sayının EBOB’u) Hepsi birden sıfır olmayan \(a, b, c\) tam sayılarının en büyük ortak böleni \(\gcd(a,b,c)\), bu üç sayının ortak bölenlerinin en büyüğü olarak tanımlanır.
a) \(\gcd(a,b,c) = \gcd\big(\gcd(a,b),\, c\big)\) olduğunu gösteriniz.
b) \(\gcd(a,b,c)\) sayısının \(ax + by + cz\) biçiminde yazılabileceğini gösteriniz.