一回りしたら元に戻る計算
剰余とは、ある数を別の数で割ったときの余りのことです。曜日や時計のように、一回りすると元に戻る計算に使います。今日から100日後が何曜日かも、余りで分かります。
同じ考え方が、バーコードの検査数字や、暗号の土台にもなっています。今日は余り、最大公約数、素数を、小さなプログラムで確かめます。
このレッスンのゴール
メモ
余りと最大公約数を使って、周期のある計算や検査数字の計算をすることができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 剰余 | 割り算の余り | 100 を 7 で割った余りは 2 |
| 合同 | 同じ数で割った余りが、等しいこと | |
| 最大公約数 | 2つの数を両方割り切る、最大の数 | |
| 互除法 | 余りを使って、最大公約数を求める手順 | |
| 素数 | 1 とその数自身でしか割り切れない、2以上の整数 | |
| 逆元 | 掛けると、余りが 1 になる数 |
学生が入力するセルは、このプレビューでは空白です。
余りで、一回りの計算をする
剰余は、割り算の余りです。Python では % で求めます。100 ÷ 7 は14あまり2なので、100 % 7 は2です。
曜日は7日で一回りします。今日が月曜日なら、100日後は、100 を7で割った余り2だけ進んで、水曜日です。
例: 今日が月曜日のとき
| 何日後 | 7で割った余り | 曜日 |
|---|---|---|
| 0日後 | 0 | 月曜日 |
| 1日後 | 1 | 火曜日 |
| 7日後 | 0 | 月曜日 |
| 10日後 | 3 | 木曜日 |
| 100日後 | 2 | 水曜日 |
| 365日後 | 1 | 火曜日 |
学生が入力するセルは、このプレビューでは空白です。
100日後、365日後、時計の計算
python3 -c "print(100 % 7, 365 % 7, (9 + 5) % 12)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
余りが同じ数は合同
2つの数を同じ数で割った余りが等しいとき、合同と呼びます。9 と 2 は、7 で割った余りがどちらも2なので、7を法として合同です。「9 ≡ 2 (mod 7)」と書きます。
足し算と掛け算は、先に余りにしてから計算しても、最後の余りは同じです。大きな数を計算するときに助かります。
先に余りにしても、答えは同じ
python3 -c "print((23 + 45) % 7, ((23 % 7) + (45 % 7)) % 7, (23 * 45) % 7, ((23 % 7) * (45 % 7)) % 7)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
検査数字は、余りで誤りを見つける
商品の13けたのコードの最後の1けたは、検査数字です。左から奇数番目の数字は1倍、偶数番目の数字は3倍にして、12けた分を足します。
その合計に検査数字を足すと、10の倍数になるように決めてあります。読みまちがいがあると10の倍数にならないので、気づけます。
例: 490123456789 の合計
| 数字 | 4 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 重み | 1 | 3 | 1 | 3 | 1 | 3 | 1 | 3 | 1 | 3 | 1 |
| 積 | 4 | 27 | 0 | 3 | 2 | 9 | 4 | 15 | 6 | 21 | 8 |
学生が入力するセルは、このプレビューでは空白です。
検査数字を計算する
# 合計は 126 です。10 で割った余りが 6 なので、4 を足すと 130 になります。
digits = "490123456789"
total = 0
for i in range(len(digits)):
if i % 2 == 0:
total = total + int(digits[i])
else:
total = total + int(digits[i]) * 3
check = (10 - total % 10) % 10
print("合計:", total, "検査数字:", check)
# digits の数字を1つ変えて、検査数字が変わるか見ましょう。
互除法で最大公約数を求める
最大公約数は、2つの数を両方割り切る、最大の数です。48 と 18 の最大公約数は6です。
互除法は、割り算の余りだけで、これを求める手順です。大きい数を小さい数で割り、余りが0になるまで、割る数と余りを次の割られる数と割る数にしてくり返します。最後に割った数が答えです。
例: 48 と 18 の互除法
| 割られる数 | 割る数 | 余り |
|---|---|---|
| 48 | 18 | 12 |
| 18 | 12 | 6 |
| 12 | 6 | 0 |
| 答え | 6 | 最後に割った数 |
学生が入力するセルは、このプレビューでは空白です。
最大公約数を3組求める
python3 -c "import math; print(math.gcd(48, 18), math.gcd(35, 12), math.gcd(100, 75))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
素数と、互いに素
素数は、1 とその数自身でしか割り切れない、2以上の整数です。2、3、5、7、11 などです。調べるには、2からその数の手前までの数で、割ってみます。
最大公約数が1の2つの数を、互いに素と呼びます。35 と 12 は、どちらも素数ではありませんが、互いに素です。
30 より小さい素数を並べる
python3 -c "print([n for n in range(2, 30) if all(n % d != 0 for d in range(2, n))])"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
「互いに素とは、2つとも素数のことだ」と考える人が多くいます。そうではありません。互いに素とは、最大公約数が1ということです。8 と 15 は、どちらも素数ではありませんが、最大公約数は1なので、互いに素です。
掛けて1になる数が逆元
7を法として、3 に掛けると余りが1になる数を探します。3 × 5 = 15 で、15 を7で割った余りは1です。この5を、7を法とした3の逆元と呼びます。
逆元があるのは、元の数と法が互いに素なときだけです。6を法とした4は、最大公約数が2なので、逆元がありません。
3 に掛けて、7 で割った余り
| x | 3 × x | 7 で割った余り |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 6 | 6 |
| 3 | 9 | 2 |
| 4 | 12 | 5 |
| 5 | 15 | 1 |
| 6 | 18 | 4 |
学生が入力するセルは、このプレビューでは空白です。
逆元を求める
python3 -c "print(pow(3, -1, 7), pow(4, -1, 9))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。