【ユークリッドの互除法は無理という人へ】不定方程式は合同式を試してみて

整数

『センターの不定方程式を簡単に解く方法ないかなぁ』『ユークリッドの互除法で答は出るけど、時間がかかるんだよなぁ』などとお悩みのあなた。

合同式を使うと、時短で解くことができます。

しかも、習得するのに要する時間もほんのわずかです。

不定方程式で困っているという人は、これから紹介する合同式をつかった計算方法を試してみてください。

スポンサーリンク

合同式の計算は余りに着目しよう

合同式の計算は余りに着目すると、見通しよく計算ができます。

実際の2018年のセンター試験本試験に出題された不定方程式の問題(の一部)を例題に解説します。

2018年センター本試験 144x-7y=1

144と7のうち、小さい方の数字に着目します。

7のほうが小さいので、mod 7 の合同式を使いますが、そのためには7で割ったときの余りに着目します。

7yは7で割り切れます。144は7×20+4と分解できるので、144xを7で割ったときの余りは4xを7で割ったときの余りと同じになります。

すなわち、左辺の144x-7yを7で割ったときの余りは、4xを7で割ったときの余りに等しくて、それが右辺の1と一致します。

ここから、4x≡1 (mod 7) となります。

ここまで、よろしいでしょうか?

このあとの計算方法が2通り考えられます。

右辺を4の倍数にあわせる

計算後半の一つ目の方法は、4x≡1 (mod 7) の右辺を4の倍数に合わせる方法です。

7で割ったときの余りが1になるのは、1以外に7つごとに無数に存在します。

4x≡1≡8≡15 (mod 7)

などとなります。小さい方にずれていくと

4x≡1≡-6≡-13 (mod 7)

などとなります。

合同式はいつでも割れるわけではないですが、mod と互いに素な数は割り算できます。

7と4は互いに素なので、4x≡8 (mod 7) の両辺を4で割って、x≡2 (mod 7) と計算できます。

これは、x は7で割ると2余る数だということを現しているので、x=7k+2 (kは整数) となります。

左辺を4以外の数になるように、同じ計算をする

もう一つの方法は、4x≡1 (mod 7) のような式をもう一本作る方法です。

右辺を合わせる方法は、この問題だとすぐに8と分かりますが、すぐにはわからない場合があることと、合同式はいつでも割れるというわけではないからです。

実際には、144を7×20+4 以外の7×□+△の形に変形します。

ここでは、144を7×21-3 と変形してみます。

すると7×21の部分は7で割り切れるので、144xを7で割ったときの余りは-3xを7で割ったときの余りと一致することがわかります。

従って、元の144x-7y=1は、-3x≡1 (mod 7) と変形できます。

あとは、4x≡1 (mod 7) と辺々加えて、x≡2 (mod 7) を得ます。

ちょっと、説明が長くなったので、端的にまとめます。

【解答】144x-7y=1 の一般解は?

スポンサーリンク

練習問題

センター試験の過去問を題材に、練習問題をやってみましょう。

過去問を使うのはいまはイヤという人は、別の問題を探してきて挑戦してみてください。

【問題】つぎの不定方程式の一般解を求めよ。
(1)$23x-31y=2$ (2018年追試)
(2)$92x+197y=1$ (2016年本試験)
(3)$92x+197y=10$ (2016年本試験)
(4)$11x+13y=1100$ (2016年追試)
(5)$11x+13y=1101$ (2016年追試)

YouTube動画解説

(1)と(4)の問題に関して、YouTubeで解説しています。(1)を解いてみたけど、しっくりこないという人などは、ぜひYouTubeも参考にしてみてください。

ユークリッドの互除法無理でも、不定方程式は合同式で裏技の如く簡単に

練習問題解答

(4)右辺の数値が大きくなっても、左辺と同じように余りがいくらになるか着目して合同式に持ち込めます。

一般解が出た後の問題も確認しておこう

2018年のセンター試験では、それまでの不定方程式の問題と違って、一般解が出たあとに手が止まってしまうような問題構成になっていました。

一般解をいかに時短で解くかはもちろん大事ですが、そのあとどんな誘導問題が続くのか、2018年の本試験と追試験だけでも再確認しておくことをおすすめします。

2019年センター試験問題解説

2019年のセンター本試験の不定方程式の問題解説動画もYouTubeにアップしましたので、こちらもご参考に (2019年2月28日追記)。

センター数学ⅠA 2019年第4問整数問題解説

コメント