高校数学をプログラミングで解く（数学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}$$の順で出てくるという法則性が見えてきますが、このような法則性が見えにくくなる場合が出てきます。このような場合、コンピュータで解くありがたみがわかると思います。演習問題に一つの例を載せたので、是非やってみてください。

読んだ感想などをお寄せください

本記事を読んだ感想や質問などを以下のお問い合せフォームからお寄せください。感想、質問をいただいた方には本記事の演習問題の解答をプレゼントします。（お問合せフォームの本文に、本記事のタイトルを入れてください。）

お問い合わせ | note（ノート）

参考文献

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

演習問題

$${11^{100}}$$を$${13}$$で割ったときの余りを求めて、その結果をコンソールに出力するプログラムを作成してください。

演習問題の解答例