Geomania.Org Forumları
Fantezi Cebir => Sayılar Teorisi => Konuyu başlatan: Metin Can Aydemir - Kasım 28, 2025, 02:19:35 ös
-
Klasik Frobenius problemi şu şekildedir: $a$ ve $b$ aralarında asal pozitif tamsayılar olsunlar. $n$ ve $m$ negatif olmayan tamsayılar olmak üzere $an+bm$'ye $a$ ve $b$'nin lineer kombinasyonu diyelim (normalde lineer kombinasyonda katsayılar negatif olabilir ama burada farklı tanımladık). $a$ ve $b$'nin lineer kombinasyonu olarak yazılamayan en büyük pozitif tamsayı $ab-a-b$'dir. Bu sayıya $a$ ve $b$'nin Frobenius sayısı denir.
Problem: $a$ ve $b$ aralarında asal pozitif tamsayılar olmak üzere, $a$ ve $b$'nin $k$ farklı lineer kombinasyonu olarak yazılamayan en büyük pozitif tamsayıya $k.$ Frobenius sayısı diyelim. $k.$ Frobenius sayısını $a$ ve $b$ cinsinden hesaplayınız. (Örneğin, $19$ sayısı $3\cdot 3+5\cdot 2$ olarak yazılabilir ve bu onun tek yazılışıdır fakat $26$ sayısı $3\cdot 2+5\cdot 4$ ve $3\cdot 7+5\cdot 1$ olmak üzere $2$ farklı şekilde yazılabilir.)
-
Öncelikle $1$. Frobenius sayısının gerçekten $ab-a-b$ olduğunu gösterelim. $S:=\langle a,b\rangle=\{an+bm: n,m\in\mathbb{Z}_{\geq 0}\}$ olarak tanımlansın ve $$\operatorname{Ap}(S,a)=\{s\in S: s-a\not\in S\}$$ olarak tanımlansın (Bu kümeye Apéry kümesi deniyor). $S$'nin elemanlarını $n$ moduna göre gruplayalım. Yeterince büyük her sayı $S$ kümesinin elemanı olacağından hiçbir küme boş küme değildir ($c>ab$ olan her tamsayı için $c\in S$'dir. Bu basit ve bilinen bir özelliktir ama en sonda bunu da ekleyeceğim.)
Kümelerin en küçük elemanlarını $s(i)$ ile gösterelim ($s(0)=0$). $n\in S$ olduğundan elemanlar $s(i)+at$ formatında olacaktır. Kümeler $$S_0=\{s(0),s(0)+a,s(0)+2a,\dots\},$$ $$S_1=\{s(1),s(1)+a,s(1)+2a,\dots\},$$ $$\vdots$$ $$S_{a-1}=\{s(a-1),s(a-1)+a,s(a-1)+2a,\dots\}$$ şeklindedir. Bu kümelerden de anlaşılacağı üzere $s-a\not\in S$ olan tüm elemanlar sadece $s(i)$ elemanlarıdır. Yani $\operatorname{Ap}(S,a)=\{0,s(1),s(2),\dots,s(a-1)\}$ formatındadır. Bu sayıların da aslında $\{0,b,2b,\dots,b(a-1)\}$ olduğunu görmek zor değildir.
$F(S)+a$ ($F(S):=$Frobenius sayısı) sayısı, tanım gereği $S$'nin elemanı olacağından $F(S)+a\in \operatorname{Ap}(S,a)=\{0,b,2b,\dots,b(a-1)\}$ olacaktır. $F(S)\not\in S$ en büyük tamsayı olduğundan $F(S)+a=b(a-1)$, yani $F(S)=ab-a-b$ olmalıdır.
Şimdi $k.$ Frobenius sayısını hesaplayalım. $c\geq F(S)+1$ olan her sayı için $c=an+bm$ olacak şekilde $n,m\geq 0$ olduğundan $c+(k-1)ab$ sayısını $$a(n+(k-1)b)+bm=a(n+(k-2)b)+b(m+a)=\cdots=an+b(m+(k-1)a)$$ olarak $k$ farklı şekilde yazabileceğimizden dolayı $(k-1)F(S)+1=kab-a-b+1$ sayısından büyük veya eşit tüm sayılar en az $k$ farklı şekilde yazılabilir. Şimdi ise $kab-a-b$'nin yazılamayacağını gösterelim. $kab-a-b=an+bm$'nin bir çözümü $(n,m)=(kb-1,-1)$'dir. Tüm çözümler, $$\dots,(kb-1,-1),((k-1)b-1,a-1),((k-2)b-1,2a-1),\dots,(b-1,(k-1)a-1),(-1,ka-1),\dots,$$ olduğundan $n$ ve $m$'nin pozitif oldukları durumlar arada kalan $k-1$ tanedir. Yani $kab-a-b$ sayısı $k$ farklı şekilde yazılamaz ama bu sayıdan büyük hepsi yazılabilir. $k.$ Frobenius sayısı $kab-a-b$'dir.
İspatta kullandığımız lemma: Eğer $c>ab$ ise $c=an+bm$ olacak şekilde $n,m\geq 0$ tamsayıları vardır.
İspat: Bezout teoreminden, $an_0+bm_0=1$ olacak şekilde $n_0$ ve $m_0$ tamsayıları vardır. Her $t$ tamsayısı için $a(n_0c+bt)+b(m_0c-at)=c$'dir. Eğer $\frac{m_0c}{a}\geq t\geq -\frac{n_0c}{b}$ olacak şekilde bir $t$ varsa $n:=n_0c+bt$ ve $m:=m_0c-at$ seçebiliriz. $t$'nin sınırları arasındaki uzaklık $\frac{c(an_0+bm_0)}{ab}=\frac{c}{ab}>1$ olduğundan bu aralıkta bir tamsayı kesinlikle vardır.