彼らは数学しか勉強できない

一次不定方程式とユークリッド互除法、そして合同式

　一次不定方程式は数ある方程式の中でも比較的簡単な部類に入るが、苦手意識を持つ人は意外と多い。

　放課後の図書室、黙々と自主勉強をしている俺を正面にいた愛華が呼んだ。

「ねぇ、ちょっといい？」

「どうした」

「これ、答え合ってる？」

　愛華はそう言って問題集とノートを開いて俺に見せた。5x＋3y＝1の整数解をすべて求める問題だ。愛華の解答はx＝－1、y＝2だった。

「間違ってはないけど問題文は『すべて求めよ』だからな。お前の解答は特殊解」

「特殊解？」

「簡単に言うと答えの一つって意味だ。これは解を一般化する必要がある」

「一般化って、ええと……式で表せってこと？」

　俺が頷くと愛華は「どうやって？」と訊いてきた。

「特殊解がx＝－1、y＝2だった。これが1に等しいんだから直接式に代入すれば、5・(－1)＋3・2＝1が成り立つ」

　5x＋3y＝1より、5x＋3y－{5・(－1)＋3・2}＝0

　5x＋3y－5・(－1)－3・2＝0　

　5x－5・(－1)＋3y－3・2＝0

　5(x＋1)＋3(y－2)=0

「んで、左辺の3(y－2)を右辺に移項させると5(x＋1)＝－3(y－2)だ。y－2は5の倍数。そしてx＋1は3の倍数、便宜上－3の倍数とする」

　整数をtとして、y－2＝5t、x＋1＝－3t

　よって、一般解はx＝－1－3t、y＝2＋5t

　俺が説明を終えると愛華は問題集の解答を確認する。それから首を傾げた。

「和人、問題集の解答x＝2＋3k、y＝－3－5kって書いてるんだけど……これ合ってるの？」

「kが整数なら正しい。不安なときは具体的な数を代入したらいい」

「じゃあ、どっちも合ってるんだ。表し方も複数あるとかややこしいなぁ」

　気持ちはまぁわからなくもない。式を満たしていれば解をどのように表わすかは解答者の自由。かなり極端だがx＝300002＋3s、y＝－500003－5s（sは整数）でもいいわけだし。さすがにそんな解答する奴はいないと思うが。

「これさ、数字が小さいからいいけど、100x＋30y＝7とかだったら普通に計算して解くの大変だよね」

「愛華、今言った式は整数の範囲では解けない」

「解けない？」

　俺は頷いた。100x＋30y＝7は左辺が10の倍数であるのに対して右辺は7の倍数。つまりこの不定方程式は整数解が存在しない。

　一次不定方程式ax＋by＝cが整数解を持つ条件は大きく分けて二つ。

　aとbが互いに素

　aとbの最大公約数がcの約数

　だから100x＋30y＝7の右辺を10の倍数、もしくはxとyの係数を互いに素にすればその式は整数解を持つ。

　そこまで説明して愛華は納得した。少し間が空いてふいに訊いてきた。

「解を持つ場合はどうやって解くの？　さすがにしらみつぶしはないよね」

「標準的な解き方としてはユークリッド互除法。俺は合同式使ってるけど」

「互除法って最大公約数を求める以外にも使えるの？」

「ああ、初見だと難しく感じると思うが何事も慣れだ。今から説明する」

　係数はやや大きいが307x＋71y＝1の解を求めてみよう。まずは307と71の最大公約数をユークリッド互除法で計算。

　307＝71・4＋23

　71＝23・3＋2

　23＝2・11＋1

　移項させて余りに着目

　1＝23－2・11

　2＝71－23・3

　23＝307－71・4

　1＝23－2・11の2に71－23・3を代入

　1＝23－(71－23・3)・11

　分配法則から、23－(－23・3・11)＋71・11　

　23－(－23・3・11)＝23・34より、1＝23・34－71・11　

　同様にして23に307－71・4を代入

　1＝23・34－71・11

　＝(307－71・4)・34－71・11

　＝307・34－71・4・34－71・11

　＝307・34＋(－71)・4・34＋11

　＝307・34＋71・(－147)

　よって、特殊解はx＝34、y＝－147

「一般解はtを整数としてx＝34＋147t、y＝－147－34t」　

「う～ん、やり方はなんとなくわかったけど計算が複雑というか……慣れるの時間かかりそう」

「まあ計算手順が視覚的に見てわかりづらいのは否めない。こればかりは練習を積むしかないな」

「和人は合同式使ってるんだよね。そっちの方が楽なの？」　

「個人的には。さっきと同じ式で解いて比較してみるか」　

　合同式で一次不定方程式を解くのは、一次合同方程式と呼ばれる方程式

　ax≡c(mod b)

　を解くのと同値である。

「307x＋71y＝1に当てはめると法を71として、307x≡1(mod 71)となる」　

「この合同方程式……だっけ？　これが307x＋71y＝1を解くのと同じなんだ」

「そう。別に307を法にしてもいいんだけど71の方が計算しやすい」

　まずは307を71で割って余りを求めると23なので、307≡23(mod 71)が成り立つ。

　合同式の四則演算は割り算の一部を除いて等式と同じように扱える。つまり、307x≡1(mod 71)は以下のようになる。

　　23x≡1(mod 71)

「xの係数を上手く調整すればxの値はすぐに求められる。たとえば左辺の係数を71にすれば右辺は当然0になる。この式からさっき求めた式を両辺を3倍にして引く」

　23x≡1(mod 71)

　69x≡3(mod 71)　両辺を3倍

　71x≡0(mod 71)より、

　71x－69x≡0－3(mod 71)

　2x≡－3≡68(mod 71)

「法が素数だからこの合同方程式は割り算が可能」

　2x≡68(mod 71)

　x≡34(mod 71)

「あとは307x＋71y＝1にx＝34を代入して、yについて解けばy＝－147が得られる」

「xを求めるだけなら合同式使った方が楽だね。yの計算が面倒だけど」

「2022年の共通テストなんかもっと面倒だぞ。yが5桁だからな」

「5桁？　どういうこと？」

「口で説明するより実際に問題見た方が早い」

　不定方程式　11（　5）x－2（　5）y＝1の整数解のうち、xが正の整数で最小になるのはx＝テト、y＝ナニヌネノである（2022年大学共通テスト数Ⅰ・A問4から引用）。

「……これホントに出題されたの？」

「ああ。誘導はついてるけど正直わからなかった」

「え、解けなかったの？」

「いや、方程式自体は合同式で解いた。誘導を使った解法がわからなかったんだ」

「何それ、誘導の意味ないじゃん」

　俺は苦笑した。計算量を考えるとこの式を解くのは断念した方がいい。xの値は不定方程式を合同方程式に変換すれば時間内でもギリ解ける。11の累乗は隣り合う桁の数字を足し合わせれば容易に求められる。平たく言えばパスカルの三角形の応用。

　11（　2）　1(1+1)1→121

　11（　3）　1(1+2)(2+1)1→1331

　11（　4）　1(1+3)(3+3)(3+1)1→14641

　11（　5）　1(1+4)(4+6)(6+4)(4+1)1→161051　繰り上がりに注意

　これを一気に32で割ってもいいが、分割した方が計算ミスを防げる。

　121≡－7(mod 32)より、

　11（　5）≡(－7)（　2）・11≡－5(mod 32)

　よって、－5x≡1(mod 32)

　32x≡0(mod 32)より、

－30x≡6(mod 32)　－5x≡1の両辺を6倍

　2x≡6(mod 32)　上の2式を足す。

　－5x≡1(mod 32)

　　6x≡18(mod 32)　2x≡6の両辺を3倍

　　x≡19(mod 32)　上の2式を足す。

　あとは根気で計算。

　11（　5）・19＝161051・19

　＝3059969

　y＝(3059969－1)/32＝95624

　よって、x＝19、y＝95624

　やはり後半がキツイ。ユークリッド互除法ではとても計算する気になれない。具体的な数字は知らないが、正答した受験生はかなり少ないのではないだろうか。というかよくこんな問題出したな。

　俺はシャーペンを机に置いて息をついた。そして今後、共通テストで同じような問題が出ないことを切に願った。