高校数学をプログラミングで解く（数学A編）「3-5 割り算の余りの性質」

マガジンリスト　＞　数学A編 3.整数の性質　＞　3-5 割り算の余りの性質

はじめに

今回は、数学Aで学ぶ「割り算の余りの性質」について、関連する問題を解くプログラムを作成します。

割り算の余りの性質

割り算の余りの性質について、説明します。

割り算の余りの性質
$${m,k}$$は正の整数、$${a,b}$$は整数とし、$${a,b}$$を$${m}$$で割った余りを、それぞれ$${r,r'}$$とする。
a. $${a+b}$$を$${m}$$で割った余りは、$${r+r'}$$を$${m}$$で割った余りに等しい。
b. $${a-b}$$を$${m}$$で割った余りは、$${r-r'}$$を$${m}$$で割った余りに等しい。
c. $${ab}$$を$${m}$$で割った余りは、$${rr'}$$を$${m}$$で割った余りに等しい。
d. $${a^k}$$を$${m}$$で割った余りは、$${r^k}$$を$${m}$$で割った余りに等しい。

割り算の余りの性質を利用する問題

では、この割り算の余りの性質を利用して解くことができる、次の問題を考えてみます。

問題
$${2^{100}}$$を$${7}$$で割ったときの余りを求めよ。

解析的な解法例

この問題は、たとえば以下のようにして解析的に解くことができます。
まず、$${2^{100}}$$は、

$$
2^{100} = 2 \cdot 2^{99} = 2 \cdot 2^{3 \cdot 33} = 2 \cdot 8^{33}
$$

と書き換えることができます。$${8}$$を$${7}$$で割った余りは$${1}$$になるので、割り算の余りの性質dを利用すると、$${8^{33}}$$を$${7}$$で割った余りは、$${1^{33}=1}$$を$${7}$$で割った余り$${1}$$と等しくなります。$${2}$$を$${7}$$で割った余りは$${2}$$で、$${8^{33}}$$を$${7}$$で割った余りは$${1}$$となることがわかったので、割り算の余りの性質cを利用すると、$${2^{100}=2\cdot 8^{33}}$$を$${7}$$で割った余りは$${2 \cdot 1=2}$$を$${7}$$で割った余り$${2}$$と等しくなります。

アルゴリズム設計

この問題をプログラミングで解くことを考えてみます。
上記の解析的な解法例のように、$${2^3=8}$$であることを利用して計算しやすくするような工夫をコンピュータにさせることは難しいです。そこで今回は、より単純な方法で計算するようにプログラミングを行います。そのために、割り算の余りの性質cを少し見直しておきます。

c'. $${rb}$$を$${m}$$で割った余りは、$${rr'}$$を$${m}$$で割った余りに等しい。

つまり、整数$${a=r}$$としても、割り算の余りの性質cは成り立ちます。
この性質c'を利用すると、この問題は次のように解くことができます。

① まず、割られる数の底$${2}$$を割る数$${7}$$で割ったときの余りを求めます。この余りは$${2}$$になります。
② ①で求めた余り$${2}$$に割られる数の底$${2}$$を掛けた数を割る数$${7}$$で割ったときの余りは、割り算の余りの性質c'を利用すると、$${2 \cdot 2 = 4}$$を割る数$${7}$$で割ったときの余り$${4}$$と等しくなります。
③ ②で求めた余り$${4}$$に割られる数の底$${2}$$を掛けた数を割る数$${7}$$で割ったときの余りは、割り算の余りの性質c'を利用すると、$${4 \cdot 2 = 8}$$を割る数$${7}$$で割ったときの余り$${1}$$と等しくなります。
④ ②や③の計算を割られる数の指数$${100}$$の数だけ繰り返すと、$${2^{100}}$$を$${7}$$で割ったときの余りを求めることができます。

プログラム

上記のアルゴリズムを利用して、$${2^{100}}$$を$${7}$$で割ったときの余りを求めてその結果をコンソールに出力するプログラムを作成します。

// 2^100を7で割ったときの余り
void setup(){

  int base = 2; // 割られる数の底
  int exponent = 100; // 割られる数の指数
  int divisor = 7; // 割る数  
 
  int remainder = 1; // 余り
  for(int i=0; i<exponent; i++){
    remainder *= base; // 余りにbaseをかける
    remainder %= divisor; // divisorで割って余りを更新
  }
  
  println(remainder);
}

ソースコード1　$${2^{100}}$$を$${m}$$で割ったときの余りを求めるプログラム

ソースコード1を、Processingの開発環境ウィンドウを開いて（スケッチ名を「calculateRemainder」としています）、テキストエディタ部分に書いて実行すると、図1のように、コンソールに$${2^{100}}$$を$${7}$$で割ったときの余りである「2」を出力します。

図1　スケッチ「calculateRemainder」の実行結果

まとめ

今回は、数学Aで学ぶ「割り算の余りの性質」について、関連する問題を解くプログラムを作成してみました。
今回扱った問題は、割り算の余りの性質dで解くことができそうですが、$${2}$$を$${7}$$で割った余りは$${2}$$ですので、割り算の余りの性質dで単純に解くことはできません。そのため、割り算の余りの性質cを少し応用したc'を利用して順番に解くことにしました。つまり、$${2}$$を$${7}$$で割った余りは$${2}$$、 $${2 \cdot 2}$$を$${7}$$で割った余りは$${4}$$、$${4 \cdot 2}$$を$${7}$$で割った余りは$${1}$$、$${1 \cdot 2}$$を$${7}$$で割った余りは$${2}$$、というように「余りに$${2}$$をかけて$${7}$$で割る」を$${100}$$回繰り返すことで解きました。
今回の問題は、余りが$${2,4,1}$$の順で出てくるという法則性が見えてきますが、もう少し大きな整数で割る場合は、このような法則性が見えにくくなる場合が出てきます。このような場合、コンピュータで解くありがたみがわかると思います。ぜひ、そのような問題を自分で見つけてプログラムしてみてください。

参考文献

改訂版 教科書傍用 スタンダード 数学A（数研出版、ISBN9784410209277）