共通テスト数学対策講座

第14講

整数の性質

剰余・互除法・合同式 ── 整数問題の3本柱

福岡先生 15分で得点源に変える

今日のゴール

Goals of this lecture

01

剰余の性質を使いこなす

$a = bq + r$ の形で整数を分解する技法

02

ユークリッドの互除法

最大公約数を高速に計算する古典的アルゴリズム

03

合同式で計算を高速化

$a \equiv b \pmod{n}$ で剰余をまとめて扱う

結論

整数は「割った余り」で世界が分かれる

剰余・互除法

余りの操作

$a = bq + r$ の繰り返しで GCD が出る

訳:余りで分類

合同式

剰余の等号

$a \equiv b \pmod{n}$ ── 余りが等しい

訳:剰余の同値類

基本性質

剰余の表現

DIVISION ALGORITHM

$a = b q + r \quad (0 \leq r < b)$

$a$:割られる数、$b$:割る数、$q$:商、$r$:余り

整数を割り算で分解。余り $r$ は $0$ 以上 $b$ 未満の整数。

具体例 ①

ユークリッドの互除法 ── $\gcd(48, 36)$

1

大きい数を小さい数で割る

$48 = 36 \cdot 1 + 12$ ── 余り $12$

2

割る数と余りで繰り返す

$36 = 12 \cdot 3 + 0$ ── 余り $0$

3

余り $0$ が出たら、その時の割る数が GCD

$\gcd(48, 36) = 12$

合同式

合同関係の定義

CONGRUENCE

$a \equiv b \pmod{n} \iff n \mid (a - b)$

($n$ で割った余りが等しい)

$a$ と $b$ の差が $n$ で割り切れる、と読む。剰余をまとめて扱う強力な道具。

合同式の性質

足し算・掛け算が普通の数と同じように

足し算

$a \equiv b, c \equiv d \Rightarrow a+c \equiv b+d$

合同式同士の和・差は、対応する辺をそのまま加減できる。

掛け算

$a \equiv b, c \equiv d \Rightarrow ac \equiv bd$

掛け算も同様。累乗 $a^n \equiv b^n \pmod{n}$ も成り立つ。

合同式は普通の等式とほぼ同じ操作ができる ── 整数計算が劇的に楽になる。

具体例 ②

$3^{100}$ を $7$ で割った余り

1

小さな累乗で剰余の周期を発見

$3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6, 3^4 \equiv 4, 3^5 \equiv 5, 3^6 \equiv 1 \pmod 7$

2

周期 6 を発見

$3^6 \equiv 1 \pmod 7$。よって $3^{6k} \equiv 1 \pmod 7$

3

$100 = 6 \cdot 16 + 4$ で分解

$3^{100} = 3^{96} \cdot 3^4 \equiv 1 \cdot 4 = 4 \pmod 7$ ── 余りは $4$

頻出パターン

整数問題の3大シーン

剰余の周期 / GCD / ディオファントス方程式が頻出

出題パターンを覚えてしまえば、本番で迷わない

3大シーン

1

剰余の周期

$a^n$ の余り → 周期を見つける

2

GCD・LCM

互除法で最大公約数。LCM=積/GCD

3

ax + by = c

不定方程式 ── 1組の解を見つけて一般解

実戦演習

共通テスト形式で確認

問 $\gcd(91, 65)$ の値は?

① $5$

② $13$ ◀ 正解

③ $7$

④ $11$

互除法:$91 = 65 \cdot 1 + 26$ → $65 = 26 \cdot 2 + 13$ → $26 = 13 \cdot 2 + 0$。最後の割る数が GCD なので $\gcd(91, 65) = 13$ ── ②。

本日のチェックリスト

反射で答えられたら習得完了

✓

剰余の表現は?

$a = bq + r$

✓

互除法の終了条件は?

余りが $0$

✓

合同式の定義は?

$a - b$ が $n$ で割り切れる

✓

合同式で足し算は?

対応する辺をそのまま加算可

✓

$3^6 \pmod 7$ は?

$1$

データの分析

平均・分散・標準偏差・相関

予習のすすめ

平均と分散の定義を確認しておくと、次回スムーズに進みます。