![見出し画像](https://assets.st-note.com/production/uploads/images/110595928/rectangle_large_type_2_94088dd20d97ee1337cf4f352c67f036.jpeg?width=1200)
高校数学をプログラミングで解く(数学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」を出力します。
![](https://assets.st-note.com/img/1689136545248-u5Im43zUgo.png?width=1200)
まとめ
今回は、数学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)
この記事が気に入ったらサポートをしてみませんか?