高校数学をプログラミングで解く（数学A編）「3-8 合同式で表される方程式」
マガジンリスト ＞ 数学A編 3.整数の性質 ＞ 3-8 合同式で表される方程式
はじめに
今回は、数学Aで学ぶ「合同式で表される方程式」について、その方程式を解くプログラムを作成します。
合同式
合同式について、解説しておきます。
合同式
$${m}$$は正の整数、$${a,b}$$を整数とする。
$${a-b}$$が$${m}$$の倍数であるとき、$${a}$$と$${b}$$は$${m}$$を法として合同であるといい、$${a \equiv b (\mathrm{mod} m)}$$と表す。$${a \equiv b (\mathrm{mod} m)}$$は$${a}$$を$${m}$$で割った余りと、$${b}$$を$${m}$$で割った余りが等しいことを表す。
合同式で表される方程式
以下では、合同式$${ax \equiv b (\mathrm{mod} m)}$$ （$${b}$$は$${m}$$より小さい自然数）を満たす$${x}$$を、$${x \equiv c (\mathrm{mod} m)}$$ （$${c}$$は$${m}$$より小さい自然数）の形で求めるプログラムを作成します。
アルゴリズム設計（解法）
合同式$${ax \equiv b (\mathrm{mod} m)}$$は言い換えると「$${ax}$$を$${m}$$で割った余りが、$${b}$$と等しい」ということになります。このことから、$${x=0, 1, \cdots , m-1}$$について、それぞれ$${ax}$$を$${m}$$で割った余りを計算し、その余りが$${b}$$に等しければ、その$${x}$$の値で合同式$${ax \equiv b (\mathrm{mod} m)}$$を満たすことがわかります。その$${x}$$の値を$${c}$$とすれば、$${x \equiv c (\mathrm{mod} m)}$$の形で求めることができます。
以下では、合同式
$$
4x \equiv 3 (\mathrm{mod} 5)
$$
について、合同式を満たす$${x}$$を求めるプログラムを考えていきます。
この場合、$${x=0,1,2,3,4}$$について、それぞれ$${4x}$$を$${5}$$で割った余りを計算していくと表1のようになります。その中で、$${4x}$$を$${5}$$で割った余りが$${3}$$に等しくなるのは$${x=2}$$のときであることがわかりますので、$${x}$$について$${x \equiv 2 (\mathrm{mod} 5)}$$と求めることができます。
表1 合同式$${4x \equiv 3 (\mathrm{mod} 5)}$$の余り
$$
\begin{array}{|c|c|c|c|c|c|}
\hline
x & 0 & 1 & 2 & 3 & 4 \\
\hline
4x & 0 & 4 & 8 \equiv 3 & 12 \equiv 2 & 16 \equiv 1 \\
\hline
\end{array}
$$
プログラム
上記で解説した解法を利用して、合同式$${ax \equiv b (\mathrm{mod} m)}$$を満たす$${x}$$を、$${x \equiv c (\mathrm{mod} m)}$$（ただし、$${c}$$は$${m}$$より小さい自然数）の形で求めるプログラムを作成します。
// ax=b(mod m)をx=c(mod m)の形で表す
void setup(){
int a = 4;
int b = 3;
int m = 5;
// x=0,1,…, m-1で
// a*xをmで割ったときの余りがbになるものを探す。
for(int x=0; x<m; x++){
if( (a*x)%m == b ){
println("x=" + x + "(mod " + m + ")");
}
}
}ソースコード1 合同式で表される方程式を解くプログラム
ソースコード1を、Processingの開発環境ウィンドウを開いて（スケッチ名を「equationofCongruence」としています）、テキストエディタ部分に書いて実行すると、図1のように、コンソールに合同式$${x \equiv c (\mathrm{mod} m)}$$の形で解を出力します。
練習問題
次の合同式を満たす$${x}$$を$${x \equiv c (\mathrm{mod} m)}$$の形で表してみましょう。まず、手計算で解いてみて、そのあとソースコード1の$${a,b,m}$$の値を変更して実行した結果と一致しているか確認してください。
① $${3x \equiv 6 (\mathrm{mod} 9)}$$
② $${3x \equiv 4 (\mathrm{mod} 5)}$$
③ $${8x \equiv 4 (\mathrm{mod} 9)}$$
④ $${5x \equiv 10 (\mathrm{mod} 15)}$$
まとめ
今回は、数学Aで学ぶ「合同式で表される方程式」について、その方程式を解くプログラムを作成してみました。
合同式で表される方程式$${ax \equiv b (\mathrm{mod} m)}$$から、「$${x=0, 1, \cdots , m-1}$$について、それぞれ$${ax}$$を$${m}$$で割った余りを計算し、その余りが$${b}$$に等しければ、その$${x}$$の値で合同式$${ax \equiv b (\mathrm{mod} m)}$$を満たす」ということを利用して$${x \equiv c (\mathrm{mod} m)}$$の形を求めました。
この方法は、問題に対して$${x=0, 1, \cdots , m-1}$$を一つ一つ当てはめて計算していき、表1のようなものを作成することで、手計算で解くことができます。ただ、$${m}$$の値が大きくなっていくと計算量が増えて、かなり大変になります。一方、このような処理はコンピュータが得意としており、$${x=0, 1, \cdots , m-1}$$を一つ一つ当てはめる計算を素早く行ってくれます。このような体験を通して、プログラミングすることの便利さを理解するとともに、プログラミングの設計力を高めていってください。
参考文献
改訂版 教科書傍用 スタンダード 数学A（数研出版、ISBN9784410209277）
この記事が気に入ったらサポートをしてみませんか？