Nighthawk 作：憑き燈
※初回は環論要素ないです。
所謂導入回で、次回はこの問題を環論の視点から解答していきます。
第D話：ベズーの補題
「本堂君、リベンジだ！」
現在、修学旅行で京都へ移動中だ。
なし崩し的に同班になった武田に話しかけられた。
「リベンジって、何の？」
「この前、君に大敗を喫してから、僕は数学の勉強に力を注いできた！さぁ、もう一度問題を出してくれ！」
「おい、武田。あまりコイツにかかわると、唐突に絶縁を宣言されるぞ」
「上杉は面白い冗談を言うね。そもそも切る縁がない相手とどうやって絶縁するの？」
上杉も同班である。絶縁とは一体なんだったのか。
「まぁ、暇つぶしにはなるだろうから、適当に問題を出してあげよう」
$ax+by=c$が整数解を持つ$ \iff c \equiv 0 \pmod g $を示せ
「$a,b,c$は0以外の整数で、$g$は$a$と$b$の最大公約数だ」
ちなみに、0を含めないようにしたのは例外処理が面白くないからで、本当は含めて考えても全く問題ない。
「移動時間は限られてるから、解説が欲しいなら早めに降参することだね」
「よし！今度こそ！」
「これ、本当に高校数学の範囲内で解けるんだろうな...」
上杉、今回は高校数学の範囲内で出題するなんて一言も言ってないよ。解けるけど。
「～っ降参だ！上杉君は？」
「俺も無理だ。右向きは示せたが、左向きが示せない。だが、$a$と$b$が互いに素のとき、$c$の部分が任意の整数になっても整数解を持つことを示せばいいはずだ。つまり、$ax+by=1$が整数解を持つことを示せば解決するんだが...」
「流石、筋がいい」
右向きは簡単。
$a= \alpha g , b= \beta g $とおけば、
$c=g (\alpha x + \beta y)$
$x,y$が整数のとき、$c$は$g$の倍数だ。
左向きは、普通に考えるのであれば上杉がやったように、
$c= \gamma g $として、
$\alpha x + \beta y = \gamma$と変形する。
このとき$\alpha$と$\beta$は互いに素だから
「$a$と$b$が互いに素、$c$が任意の整数のとき、$ax+by=c$が整数解を持つ」を示すのと変わらない。
そしてこれは「$a$と$b$が互いに素のとき、$ax+by=1$が整数解を持つ」と同値だ。
「要するに、$b$で割ったら1余るような$a$の倍数が存在すればいいんでしょ？答えはすぐそこだよ」
「って言われてもな...」
「僕にもさっぱり...」
「ヒント、フェルマーの小定理、群論を使わない方の証明」
「...あっ！」
「え？何？」
「そうか、そういうことか！」
そう、気付いてしまえば簡単な話だ。
$a,2a,3a,\cdots ,(b-1)a$をそれぞれ$b$で割ったときの余りは、すべてバラバラだ。
もし余りが同じ$ia$と$ja$(ただし$i \gt j$)が存在すると仮定した場合
$(i-j)a \equiv 0 \pmod b$
$a$と$b$は互いに素だから
$i-j \equiv 0 \pmod b$であり
$1 \leqq i-j \leqq b-2$より矛盾する
「つまり、$b$で割ったら1余るような$a$の倍数は必ず存在する！」
「なるほど...なんだか狐につままれたような証明だね」
「実はこんな回りくどいことしなくても左向きは直接証明できるけどね」
唐突な爆弾発言である。
「は？」
「え？」