ウソブックス:aとbが互いに素で、あるときのaとbだけの和で表せない最大の整数がab-(a+b)であることの雑な説明

事実を書きすぎな記事この記事は嘘やユーモアも含まれてはいますが、8割方は事実を書いています。
ユーモアを付け足してくれる方を募集しています。

Twitterのトレンドになっていたから、自分も参加、証明はウソペディアらしく雑(だって嘘でも良いんだし。)表を元にした説明でも別に良いかなーと。かるーい読み物に　タイトルの問題は、フロベニウスの硬貨交換問題として有名である。

フロベニウスの硬貨交換問題

見栄の為出来るだけ高価な互いに素な数種類の硬貨で、釣は取っときなと言いながら、釣り銭が出ないように、少額決済を繰り返す、エクストリームスポーツである。硬貨が3種類以上の場合の公式は未だ見つかっておらず、硬貨の種類に対して多項式時間で解けるアルゴリズムも見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である。一方で、2種類である場合は、以下のようにして、比較的容易に釣銭が出ない条件を定式化することができる。

硬貨の切手バージョンの問題として、郵政公社により切手販売促進の為、シルベスターの切手問題なるキャンペーンが開始されたが、郵政民営化により廃止された。

Twitterのトレンドに乗っかる

aとbが互いに素で、あるときのaとbだけの和$ma+nb(m,n\in \mathbb {Z} ,m,n\geq 0)$で表せない最大の整数がab-(a+b)であることの、屁理屈。

$a,b$が、有限$a<b$としても一般性は失われない。

まず、 $k_{1}=1,k_{2}=2,\cdots$として自然数を

$ak_{1}-(a-1),ak_{1}-(a-2),\cdots ,ak_{1}-1,ak_{1}$

$ak_{2}-(a-1),ak_{2}-(a-2),\cdots ,ak_{2}-1,ak_{2}$

$\vdots$

$a(b-1)-(a-1),a(b-1)-(a-2),\cdots ,a(b-1)-1,a(b-1)$

$ab-(a-1),ab-(a-2),\cdots ,ab-1,ab$

$\vdots$

という形の行列に分ける。

同列にある隣接行の成分の差は常に$+a$であるから、ある$k=k_{i}$において、$ak_{i}-(a-l)\equiv 0{\pmod {b}}$、つまり$ak_{i}-(a-l)$が$b$の倍数になったとすると、任意の$k\geq k_{i}$において、$ak-(a-l)=(k-k_{i})a+nb(k,n\in \mathbb {Z} ,k,n\geq 0)$の形で表すことができる。…(＊)

ここで、$a$と$b$が互いに素である時、

$b,2b,\cdots ,(a-1)b,ab$を$a$で割った余りは全て異なり、その集合は明らかに$\{0,1,2,\cdots ,a-1\}$の$a$個の非負整数で構成されているから、全ての$ak_{n}$以外の列に$b$の倍数が入るには、$(a-1)b$までを計算すれば十分である。

ここで、$ab-b$までの自然数において、$ma+nb(m,n\in \mathbb {Z} ,m,n\geq 0)$で表現されない数を考慮するにあたっては、$a$の倍数$ak_{n}$の列は明らかに除外してよい。

$ab-b$の列と、$a$の倍数列以外の列については、$a<b$より各行に$b$の倍数は高々1回しか出現しないことから、$ab-b$の存在する行よりも上の行、かつ、$x\leq ab-2b<ab-b-a=ab-(a+b)$を満たすある$x\in \mathbb {N}$について、$b$の倍数となる。

このことと(＊)より、$ab-b$の一つ上の行の時点で、$ak_{n}$と$ab-b$の列以外の全ての列に$b$の倍数が出現しており、かつ$ab-(a+b)<x<ab-b$の区間に存在する$x$については、各$x$の一つ上以上のどこかの行に存在する$b$の倍数と同列ということになるため、やはり$ma+nb(m,n\in \mathbb {Z} ,m,n\geq 0)$の形で表現することができる。

故に、求める数は、$ab-b$と同列で一つ上の行に存在する数であり、この数には、$ab-b$から$a$を引けば到達するので、

求める数は$ab-(a+b)$となる。

イメージ図

$(a,b)=(5,7)$の場合	1	2	3	4	5
$k=1$	$5\times 1-4=1$	$5\times 1-3=2$	$5\times 1-2=3$	$5\times 1-1=4$	${\bcancel {5}}$
$k=2$	$5\times 2-4=6$	$5\times 2-3=\!\!\!{\bcancel {7}}\!\!=ab-4b$	$5\times 2-2=8$	$5\times 2-1=9$	${\bcancel {10}}$
$k=3$	$5\times 3-4=11$	$5\times 3-3=\!\!\!{\bcancel {12}}$	$5\times 3-2=13$	$5\times 3-1=\!\!\!{\bcancel {14}}\!\!=ab-3b$	${\bcancel {15}}$
$k=4$	$5\times 4-4=16$	$5\times 4-3=\!\!\!{\bcancel {17}}$	$5\times 4-2=18$	$5\times 4-1=\!\!\!{\bcancel {19}}$	${\bcancel {20}}$
$k=5$	$5\times 5-4=\!\!\!{\bcancel {21}}\!\!=ab-2b$	$5\times 5-3=\!\!\!{\bcancel {22}}$	$5\times 5-2=\color {red}23=ab-(a+b)$	$5\times 5-1=\!\!\!{\bcancel {24}}$	${\bcancel {25}}$
$k=6$	$5\times 6-4=\!\!\!{\bcancel {26}}$	$5\times 6-3=\!\!\!{\bcancel {27}}$	$5\times 6-2=\!\!\!{\bcancel {28}}\!\!=ab-b$	$5\times 6-1=\!\!\!{\bcancel {29}}$	${\bcancel {30}}$
$k=7$	$5\times 7-4=\!\!\!{\bcancel {31}}$	$5\times 7-3=\!\!\!{\bcancel {32}}$	$5\times 7-2=\!\!\!{\bcancel {33}}$	$5\times 7-1=\!\!\!{\bcancel {34}}$	${\bcancel {35}}=ab$