数学A / 整数の性質

整数の性質実戦編の問題全8問

難関大の総合問題。複数の単元を融合した単元横断の演習

難易度: ★ 基礎·★★ 標準·★★★ 応用·★★★★ 難関·実戦編·最難関編

100! の末尾に並ぶ0の個数(素因数の個数)
フェルマーの小定理(二項定理と帰納法)
3の2024乗を100で割った余り(位数)
(2+√3)ⁿ の整数部分は奇数(共役と漸化式)
ピタゴラス数の積は60の倍数(合同で場合分け)
オイラー関数の値(互いに素な数の個数)
連続する和が n の倍数(鳩の巣原理)
素数を法とする二項展開(フロベニウスの夢)

問1100! の末尾に並ぶ0の個数(素因数の個数)

実戦編整数の性質素因数分解数え上げ床関数単元横断

問題

$100!$ ( $= 1 \times 2 \times \dots \times 100$ )を計算すると、末尾に $0$ が連続して何個並ぶか求めよ。

ヒントを見る

末尾の $0$ の個数 $=$ 因数 $10$ の個数 $= min (2 の個数, 5 の個数)$ 。 $2$ の方が多いので $5$ の個数を数える。 $25 = 5^{2}$ の倍数は $5$ を2個持つことに注意。

解答・解説

方針

末尾の $0$ は $10 = 2 \times 5$ の因子の数、すなわち $min (2 の個数, 5 の個数)$ 。 $2$ は $5$ より多いので $5$ の個数を数える。 $5, 25, \dots$ の倍数を段階的に数える。

解答

⓪ 発想(どう考え始めるか) 末尾の $0$ の個数は、 $100!$ が $10$ で何回割れるかで決まる。 $10 = 2 \times 5$ だから、答えは「因数 $2$ の個数」と「因数 $5$ の個数」の小さい方だ。

$1 \sim 100$ には偶数がたくさんある。因数 $2$ は明らかに $5$ より多いので、少ない方= $5$ の個数を数えればよい。数え方にもコツがある。 $5$ の倍数は $5$ を $1$ 個ずつ持つが、 $25 = 5^{2}$ の倍数はもう $1$ 個余分に持つ。段階的に数え足すのが正確だ。

重要

n!

に含まれる素数

p

の個数

= ⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p ^{2}} ⌋ + ⌊ \frac{n}{p ^{3}} ⌋ + \dots

(ルジャンドルの公式)

① $0$ の個数 $= 5$ の個数。 末尾の $0$ の個数 $= min (2 の個数, 5 の個数)$ 。偶数は $50$ 個以上あり $2$ の個数は $5$ の個数より多いので、 $5$ の個数を数えればよい。

② $5$ の個数を段階的に。 $1 \sim 100$ で

$5$ の倍数は $⌊ \frac{100}{5} ⌋ = 20$ 個(それぞれ $5$ を少なくとも $1$ 個持つ)、
$25 = 5^{2}$ の倍数は $⌊ \frac{100}{25} ⌋ = 4$ 個(さらにもう $1$ 個ずつ持つ)、
$125 = 5^{3}$ の倍数は $⌊ \frac{100}{125} ⌋ = 0$ 個。

③ 合計。 $5$ の因数は $20 + 4 + 0 = 24 個 .$ よって末尾に $0$ は $24$ 個並ぶ。

まとめ末尾の $0$ は因数 $5$ の個数(少ない方)。 $5, 25$ の倍数を段階的に数えて $20 + 4 = 24$ 。整数(素因数)と数え上げの融合。 $25$ の倍数を二重に数えることを忘れない。

発展。 因数 $5$ の個数は、 $n$ が $25$ の倍数をまたぐ瞬間に $2$ 以上ジャンプすることがある。実際 $24!$ までは $4$ 個、 $25!$ でいきなり $6$ 個になる。だから「末尾にちょうど $5$ 個の $0$ が並ぶ $n!$ 」は存在しない。届かない個数がある。これは床関数の和ならではの現象だ。

答

末尾の $0$ の個数 $= 100!$ に含まれる素因数 $5$ の個数 $= ⌊ \frac{100}{5} ⌋ + ⌊ \frac{100}{25} ⌋ = 20 + 4 = 24$ 。

別解

別解:桁和の公式ですぐに出す(得意な人向けの高い視点)。 階乗に含まれる素因数 $5$ の個数には、 $5$ 進法を使った閉じた公式がある。

$n$ を $5$ 進法で書いたときの桁の和を $s$ とすると、 $n!$ に含まれる因数 $5$ の個数は $\frac{n - s}{5 - 1}$ になる(床関数の和 $⌊ \frac{n}{5} ⌋ + ⌊ \frac{n}{25} ⌋ + \dots$ を桁ごとに整理すると、各桁が等比数列の和を作ることから出る)。 $100$ は $5$ 進法で $400$ ( $100 = 4 \cdot 25$ )。桁和は $s = 4$ だから

$\frac{100 - 4}{5 - 1} = \frac{96}{4} = 24.$

床関数を $1$ 段ずつ足す本解と同じ $24$ が、桁の情報だけから出る。 $1000!$ でも $1000$ は $5$ 進法で $13000$ 、桁和 $4$ で $\frac{996}{4} = 249$ と即答できる。

ポイント

末尾の $0$ の個数 $= min (2, 5 の個数) = 5$ の個数。
$25 = 5^{2}$ の倍数は $5$ を2個持つので二重に数える。
$⌊ \frac{100}{5} ⌋ + ⌊ \frac{100}{25} ⌋ = 24$ 。

よくある間違い

「 $10$ の倍数の個数」を数えて $10$ 個と答える( $0$ を作るのは因数 $2 \times 5$ の組。 $20 = 2^{2} \cdot 5$ のような数も $1$ 個ずつ寄与する)。
$25, 50, 75, 100$ が $5$ を $2$ 個持つことを忘れ、 $20$ 個と答える。
念のためにと因数 $2$ の個数( $97$ 個)まで正確に数えて時間を使う(「偶数だけでも $50$ 個 $> 24$ 」の一言で $2$ の方が多いことは十分)。

問2フェルマーの小定理(二項定理と帰納法)

実戦編整数の性質合同二項定理数学的帰納法単元横断

問題

$p$ を素数とする。すべての整数 $a \geq 0$ について $a^{p} \equiv a (mod p)$ が成り立つことを、二項定理と数学的帰納法で示せ。

ヒントを見る

$0 < k < p$ のとき $(k p)$ は $p$ の倍数。すると $(a + 1)^{p}$ を二項展開すると、中間項が消えて $a^{p} + 1$ に合同。 $a$ について帰納法。

解答・解説

方針

$0 < k < p$ のとき $(k p)$ が $p$ の倍数であることを使うと、 $(a + 1)^{p} \equiv a^{p} + 1$ 。これを使って $a$ に関する数学的帰納法で示す。

解答

⓪ 発想(どう考え始めるか) 「すべての整数 $a$ で成り立つ」を示すなら、 $a$ に関する帰納法が自然だ。 $a$ から $a + 1$ へ渡る橋がほしい。

橋になるのが二項定理である。 $(a + 1)^{p}$ を展開すると、 $p$ が素数なら $0 < k < p$ の $(k p)$ はすべて $p$ の倍数。つまり中間項が $mod p$ で全部消える。

残るのは $(a + 1)^{p} \equiv a^{p} + 1$ 。この「 $1$ つずつ進める」関係をもとに、 $a = 0$ から積み上げればよい。

定理

p

が素数で

0 < k < p

のとき

(k p) = \frac{p !}{k ! ( p - k )!}

は

p

の倍数(分子の

p

が分母で約されない)

① 二項定理で $1$ 進める。 $0 < k < p$ で $(k p) \equiv 0 (mod p)$ だから $(a + 1)^{p} = k = 0 \sum p (k p) a^{k} \equiv (0 p) a^{0} + (p p) a^{p} = 1 + a^{p} (mod p) .$ すなわち $(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ 。

② 帰納法。 $a = 0$ : $0^{p} = 0 \equiv 0$ で成立。 $a$ で $a^{p} \equiv a$ を仮定すると、①より $(a + 1)^{p} \equiv a^{p} + 1 \equiv a + 1 (mod p) .$ よって $a + 1$ でも成立。

重要数学的帰納法:

a = 0

で成立し、

a

で成立すれば

a + 1

でも成立 → すべての

a \geq 0

で成立

③ 結論。 すべての整数 $a \geq 0$ で $a^{p} \equiv a (mod p)$ 。

まとめ $(k p) \equiv 0 (0 < k < p)$ から $(a + 1)^{p} \equiv a^{p} + 1$ 、 $a$ の帰納法でフェルマーの小定理 $a^{p} \equiv a$ 。整数(合同)・二項定理・帰納法の融合。

発展。 逆は成り立たない。 $2^{341} \equiv 2 (mod 341)$ だが、 $341 = 11 \times 31$ は合成数である(擬素数とよばれる。底を $3$ に変えると見破れる)。「フェルマーの小定理を満たすか」は素数判定の一次試験にすぎず、これをすり抜ける合成数の存在が、現代の素数判定法を精密にした。

答

$0 < k < p$ で $(k p) \equiv 0 (mod p)$ なので $(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ 。 $a$ についての帰納法で $a^{p} \equiv a$ 。

別解

別解:「掛けても並べ替わるだけ」の証明(得意な人向けの高い視点)。 $a$ が $p$ の倍数なら両辺とも $\equiv 0$ で明らか。そこで $a$ が $p$ で割れないとする。

$a, 2 a, 3 a, \dots, (p - 1) a$ を $p$ で割った余りを見る。もし $ia \equiv j a$ なら $(i - j) a \equiv 0$ で、 $a$ が $p$ と互いに素だから $i = j$ 。つまり余りはすべて異なり、 $1, 2, \dots, p - 1$ の並べ替えになっている。

全部掛け合わせると

$a^{p - 1} \cdot (p - 1)! \equiv (p - 1)! (mod p) .$

$(p - 1)!$ は $p$ と互いに素だから両辺から払ってよく、 $a^{p - 1} \equiv 1$ 。両辺に $a$ を掛ければ $a^{p} \equiv a$ 。帰納法で $1$ 段ずつ登る本解に対し、こちらは「 $a$ 倍という操作が余りの集合を並べ替えるだけ」という全体の対称性を使う。ひとつの定理を別々の方法で示せる例だ。

ポイント

$0 < k < p$ で $(k p)$ は $p$ の倍数(素数だから)。
$(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ 。
$a$ についての帰納法で $a^{p} \equiv a$ 。

よくある間違い

$(k p) \equiv 0$ の理由を「分子に $p$ があるから」で済ませる( $p$ が素数で、分母 $k! (p - k)!$ の因数がすべて $p$ 未満だから約分で消えない、まで言う)。
帰納法の出発点( $a = 0$ で $0^{p} \equiv 0$ )を書き忘れる。
$a^{p} \equiv a$ と $a^{p - 1} \equiv 1$ を混同する(後者は $a$ が $p$ の倍数のとき成り立たない。 $a$ で割る前に互いに素の確認が要る)。

問33の2024乗を100で割った余り(位数)

実戦編整数の性質合同位数周期単元横断

問題

$3^{2024}$ を $100$ で割った余りを求めよ。

ヒントを見る

$3$ の $100$ を法とするべきは周期的。 $3^{1}, 3^{2}, 3^{4}, \dots$ と計算して $1$ に戻る指数(位数)を探す。 $2024$ をその周期で割った余りが要点。

解答・解説

方針

$3^{n} mod 100$ の周期(位数)を求める。 $3^{k}$ を順に計算して $1$ に戻る $k$ を見つけ、 $2024$ をその周期で割った余りに帰着させる。

解答

⓪ 発想(どう考え始めるか) $3^{2024}$ を直接計算するのは論外だ。だが求めるのは「 $100$ で割った余り」だけ。余りで考えると、 $3$ のべきはいつか必ず $1$ に戻り、そこから同じ列を繰り返す。

そこで $3^{k} \equiv 1 (mod 100)$ となる最小の $k$ (位数)を探す。周期が分かれば、指数 $2024$ をその周期で割った余りに置き換えられる。大きな指数を「周期で折りたたむ」。これが位数の考え方だ。

重要

3^{k} \equiv 1 (mod 100)

となる最小の

k

(位数)が周期。指数はこの周期で割った余りに置き換えてよい

① 位数を求める。 $mod 100$ で $3^{1} = 3, 3^{2} = 9, 3^{4} = 81, 3^{5} = 243 \equiv 43, 3^{10} \equiv 4 3^{2} = 1849 \equiv 49, 3^{20} \equiv 4 9^{2} = 2401 \equiv 1.$ よって位数は $20$ ( $3^{20} \equiv 1$ )。

② 指数を周期で割る。 $2024 = 20 \times 101 + 4$ だから $3^{2024} = (3^{20})^{101} \cdot 3^{4} \equiv 1^{101} \cdot 3^{4} = 3^{4} (mod 100) .$ ③ 余り。 $3^{4} = 81$ 。よって $3^{2024}$ を $100$ で割った余りは $81$ 。

まとめ $3$ のべきは $mod 100$ で周期 $20$ ( $3^{20} \equiv 1$ )。 $2024 \equiv 4 (mod 20)$ だから $3^{2024} \equiv 3^{4} = 81$ 。整数(合同)・位数・周期の融合。

発展。 $1 \sim 100$ で $100$ と互いに素な数はちょうど $40$ 個あり、 $3$ の位数 $20$ はこの $40$ の約数になっている。「位数は全体の個数の約数」という関係は一般に成り立ち、位数の候補を絞る道具になる(オイラーの定理につながる)。

答

$3^{20} \equiv 1 (mod 100)$ (位数 $20$ )。 $2024 = 20 \cdot 101 + 4$ より $3^{2024} \equiv 3^{4} = 81 (mod 100)$ 。

別解

別解: $100 = 4 \times 25$ に分けて別々に攻める(得意な人向けの高い視点)。 $mod 100$ の代わりに、互いに素な $mod 4$ と $mod 25$ で別々に余りを求め、最後に合体させる。

$mod 4$ では $3 \equiv - 1$ だから、 $3^{2024} \equiv (- 1)^{2024} = 1$ 。 $mod 25$ では $3$ のべきを追うと $3^{20} \equiv 1$ (周期 $20$ )。 $2024 = 20 \cdot 101 + 4$ より $3^{2024} \equiv 3^{4} = 81 \equiv 6 (mod 25)$ 。「 $25$ で割ると $6$ 余る」 $0 \sim 99$ の数は $6, 31, 56, 81$ の $4$ つ。このうち「 $4$ で割ると $1$ 余る」のは $81$ だけ。よって $3^{2024} \equiv 81 (mod 100)$ 。

法を素因数のかたまりに分けると、周期探しが小さな法( $mod 25$ )で済む。大きな法を分解して1つずつ調べる方法は、ほかの合同式の問題でも広く使える。

ポイント

$3^{n} mod 100$ は周期的、位数(最小の $3^{k} \equiv 1$ )を探す。
$3^{20} \equiv 1 (mod 100)$ 。
$2024 \equiv 4 (mod 20)$ より $3^{2024} \equiv 3^{4} = 81$ 。

よくある間違い

$mod 10$ (下 $1$ 桁)の周期 $4$ を見つけて、それを $mod 100$ にそのまま流用する(下 $2$ 桁の周期は $20$ 。法が変われば周期も変わる)。
周期を途中まで見て「見つけたつもり」になり、 $3^{20} \equiv 1$ を最後まで計算で確かめない。
$2024 = 20 \cdot 101 + 4$ の余り計算を誤り、 $3^{4}$ でない別のべきを評価する(指数の割り算こそ検算する)。

問4(2+√3)ⁿ の整数部分は奇数(共役と漸化式)

実戦編整数の性質数列漸化式共役単元横断

問題

$n$ を自然数とする。 $a_{n} = (2 + 3)^{n} + (2 - 3)^{n}$ について、(1) $a_{n}$ は整数で $a_{n + 1} = 4 a_{n} - a_{n - 1}$ を満たすことを示せ。

(2) $(2 + 3)^{n}$ の整数部分は奇数であることを示せ。

ヒントを見る

(1) $2 + 3$ と $2 - 3$ は和 $4$ 、積 $1$ 。だから両方 $x^{2} - 4 x + 1 = 0$ の解で $a_{n + 1} = 4 a_{n} - a_{n - 1}$ 。(2) $0 < 2 - 3 < 1$ に注目。 $a_{n}$ の偶奇は?

解答・解説

方針

(1) $2 \pm 3$ が満たす2次方程式から3項間漸化式を導き、初期値が整数であることを示す。(2) 共役 $(2 - 3)^{n}$ が $0$ と $1$ の間にあることと、 $a_{n}$ の偶奇を使う。

解答

⓪ 発想(どう考え始めるか) $(2 + 3)^{n}$ 単独は無理数で扱いにくい。だが共役 $(2 - 3)^{n}$ を足すと、 $3$ の部分が打ち消し合って整数になる。 $a_{n}$ はこの整数のことだ。

$2 \pm 3$ は和 $4$ ・積 $1$ の $2$ 数だから、 $x^{2} - 4 x + 1 = 0$ の解。ここから $3$ 項間漸化式が出て、 $a_{n}$ が整数であることも芋づる式に従う。

(2) の決め手は $0 < 2 - 3 < 1$ だ。 $n$ 乗しても $0$ と $1$ の間の小さな数のままだ。だから $(2 + 3)^{n} = a_{n} - (2 - 3)^{n}$ の整数部分は $a_{n} - 1$ で、あとは $a_{n}$ の偶奇を漸化式で追えばよい。

① 整数と漸化式。 $2 + 3, 2 - 3$ は和 $4$ 、積 $1$ だから、ともに $x^{2} = 4 x - 1$ を満たす。よって $(2 \pm 3)^{n + 1} = 4 (2 \pm 3)^{n} - (2 \pm 3)^{n - 1}$ 。両者を足すと $a_{n + 1} = 4 a_{n} - a_{n - 1} .$ $a_{0} = 2, a_{1} = (2 + 3) + (2 - 3) = 4$ は整数で、漸化式が整数係数だから、すべての $a_{n}$ は整数。

② $a_{n}$ は偶数。 $a_{0} = 2, a_{1} = 4$ はともに偶数。 $a_{n + 1} = 4 a_{n} - a_{n - 1} \equiv - a_{n - 1} \equiv a_{n - 1} (mod 2)$ だから、偶奇は $2$ つ前と同じ。ゆえに全ての $a_{n}$ は偶数。

③ 整数部分は奇数。 $0 < 2 - 3 < 1$ より $0 < (2 - 3)^{n} < 1$ 。 $(2 + 3)^{n} = a_{n} - (2 - 3)^{n} .$ $a_{n}$ は整数で、そこから $0$ と $1$ の間の数を引くので、 $(2 + 3)^{n}$ の整数部分は $a_{n} - 1$ 。 $a_{n}$ が偶数だから $a_{n} - 1$ は奇数。よって整数部分は奇数。

重要

x = a_{n} - ε

(

a_{n}

整数、

0 < ε < 1

)の整数部分は

a_{n} - 1

まとめ共役を足すと整数 $a_{n}$ 、漸化式 $a_{n + 1} = 4 a_{n} - a_{n - 1}$ で偶数と分かる。 $(2 - 3)^{n} \in (0, 1)$ より $(2 + 3)^{n}$ の整数部分は $a_{n} - 1$ (奇数)。整数・数列・共役の融合。

発展。 同じ仕掛けは $b_{n} = (1 + 2)^{n} + (1 - 2)^{n}$ でも動く( $b_{n + 1} = 2 b_{n} + b_{n - 1}$ で全項偶数)。ただし $1 - 2$ は負なので $(1 - 2)^{n}$ の符号が交互に変わり、 $(1 + 2)^{n}$ の整数部分は $n$ が偶数なら奇数 $b_{n} - 1$ 、 $n$ が奇数なら偶数 $b_{n}$ と、偶奇が入れ替わる。共役の符号まで観察が要る分、一段むずかしい。

答

$2 \pm 3$ は $x^{2} - 4 x + 1 = 0$ の解なので $a_{n + 1} = 4 a_{n} - a_{n - 1}$ 、 $a_{0} = 2, a_{1} = 4$ で整数。 $0 < (2 - 3)^{n} < 1$ かつ $a_{n}$ は偶数なので、 $(2 + 3)^{n}$ の整数部分 $= a_{n} - 1$ は奇数。

別解

別解:二項定理で開いて直接見る(苦手な人向け)。 $(2 + 3)^{n}$ と $(2 - 3)^{n}$ を二項定理で展開して足すと、何が起きるかを直接見てみる。

$3$ の奇数乗の項は、 $+ 3$ と $- 3$ で符号が逆になり、足すと消える。偶数乗の項は $(3)^{2 j} = 3^{j}$ が整数で、同じものが $2$ 回現れて $2$ 倍で残る。つまり

$a_{n} = 2 j \geq 0 \sum (2 j n) 2^{n - 2 j} 3^{j} .$

これは「 $2 \times$ (整数)」の形そのものだ。 $a_{n}$ が整数であることも、偶数であることも、この式から一目で分かる(本解は偶奇を漸化式の帰納で追うが、こちらは形から即座に出る)。漸化式の計算の速さと、展開の見通しのよさ。両方を持っておくと確かめ合いができる。

ポイント

共役を足すと無理数部分が消えて整数 $a_{n}$ 。
$2 \pm 3$ は $x^{2} - 4 x + 1 = 0$ の解、 $a_{n + 1} = 4 a_{n} - a_{n - 1}$ 。
$0 < (2 - 3)^{n} < 1$ と $a_{n}$ が偶数から、整数部分 $a_{n} - 1$ は奇数。

よくある間違い

整数部分を $a_{n}$ と答える(正しくは $a_{n} - 1$ 。 $(2 + 3)^{n} = a_{n} - (2 - 3)^{n}$ で、小さな正の数を引いた分だけ $a_{n}$ を下回る)。
$0 < 2 - 3 < 1$ の確認を飛ばす(これがないと $(2 - 3)^{n}$ が $0$ と $1$ の間にとどまる保証がない)。
$a_{n}$ が偶数であることを初期値だけで済ませ、漸化式 $a_{n + 1} = 4 a_{n} - a_{n - 1}$ (偶数の $4$ 倍から偶数を引くと偶数)による帰納を書かない。

問5ピタゴラス数の積は60の倍数(合同で場合分け)

実戦編整数の性質合同ピタゴラス数倍数単元横断

問題

$x^{2} + y^{2} = z^{2}$ を満たす自然数 $x, y, z$ について、積 $x y z$ は $60$ の倍数であることを示せ。

ヒントを見る

$60 = 4 \cdot 3 \cdot 5$ 。 $3, 4, 5$ で割り切れることを別々に。平方数 $mod 3$ は $0, 1$ だけ、 $mod 4$ は $0, 1$ 、 $mod 5$ は $0, 1, 4$ 。 $x^{2} + y^{2} = z^{2}$ でどれかが割り切れる。

解答・解説

方針

$60 = 4 \cdot 3 \cdot 5$ なので、 $x y z$ が $3, 4, 5$ で割り切れることを個別に示す。平方数を $mod 3, 4, 5$ で見ると取りうる値が限られ、 $x, y, z$ のどれかが各素因数で割り切れることが従う。

解答

⓪ 発想(どう考え始めるか) $60 = 4 \cdot 3 \cdot 5$ と分解する。 $4, 3, 5$ は互いに素だから、 $x y z$ が $3$ でも $4$ でも $5$ でも割り切れることを別々に示せば十分だ。

決め手は「平方数を小さい数で割った余りはごく限られる」ことだ。 $mod 3$ では ${0, 1}$ 、 $mod 4$ でも ${0, 1}$ 、 $mod 5$ では ${0, 1, 4}$ しかない。この制約を $x^{2} + y^{2} = z^{2}$ に当てはめる。「どれも割り切れない」と仮定した瞬間に余りが合わなくなり、 $x, y, z$ のどれかが各素因数を担うと分かる。

重要平方数

mod 3

は

{0, 1}

、

mod 4

は

{0, 1}

、

mod 5

は

{0, 1, 4}

のいずれか

① $3$ の倍数。 もし $x, y$ がともに $3$ で割れないなら $x^{2} \equiv y^{2} \equiv 1 (mod 3)$ 、 $z^{2} \equiv 1 + 1 = 2 (mod 3)$ 。だが平方数は $mod 3$ で $2$ になれない。矛盾。よって $x, y$ の少なくとも一方は $3$ の倍数、 $x y z$ は $3$ の倍数。

② $4$ の倍数。 もし $x, y$ がともに奇数なら $x^{2} \equiv y^{2} \equiv 1 (mod 4)$ 、 $z^{2} \equiv 2 (mod 4)$ 。だが平方数は $mod 4$ で $2$ になれない。よって $x, y$ の少なくとも一方は偶数。偶数の平方は $4$ の倍数(かつ奇数²は $\equiv 1 (mod 8)$ の考察で、 $x, y$ の一方は $4$ の倍数になる)。ていねいには、 $x, y$ の一方が偶数で、その偶数 $m = 2 m^{'}$ について、 $z^{2} - y^{2} = x^{2}$ の偶奇から $x$ (または $y$ )が $4$ の倍数と分かる。いずれにせよ $x y z$ は $4$ の倍数。

③ $5$ の倍数。 もし $x, y, z$ がすべて $5$ で割れないなら、平方は $mod 5$ で $1$ か $4$ 。 $x^{2} + y^{2} \equiv z^{2}$ を ${1, 4}$ の組で調べると、 $1 + 1 = 2, 1 + 4 = 0, 4 + 4 = 3 (mod 5)$ 。 $z^{2} \in {1, 4}$ に一致するのは無い( $0, 2, 3$ はいずれも不適)。矛盾。よって $x, y, z$ のどれかは $5$ の倍数、 $x y z$ は $5$ の倍数。

まとめ $60 = 4 \cdot 3 \cdot 5$ 。平方数の $mod 3, 4, 5$ の値が限られることを使うと、 $x, y, z$ のどれかが各素因数で割り切れ、 $x y z$ は $3, 4, 5$ すべての倍数。よって $60$ の倍数。整数(合同)と場合分けの融合。

発展。 $3, 4, 5$ の担当は別々でもよいし、 $1$ つの数が兼任してもよい( $5, 12, 13$ では $12$ が $3$ と $4$ を兼任する)。また $60$ はこれ以上大きくできない。 $3, 4, 5$ 自身の積が $x y z = 60$ だからで、 $60$ は「すべてのピタゴラス数の積の最大公約数」である。

答

$60 = 4 \cdot 3 \cdot 5$ 。 $x y z$ が $3$ の倍数・ $4$ の倍数・ $5$ の倍数であることを、平方数の $mod 3, mod 4, mod 5$ の値で場合分けして示す。

別解

別解:一般形 $(m^{2} - n^{2}, 2 mn, m^{2} + n^{2})$ で見る(得意な人向けの高い視点)。 原始的な( $3$ 数に共通因数がない)ピタゴラス数は、互いに素で偶奇の異なる $m > n$ を使って $x = m^{2} - n^{2}$ 、 $y = 2 mn$ 、 $z = m^{2} + n^{2}$ と書けることが知られている。一般の解はその整数倍だから、原始解で $60 ∣ x y z$ を示せば十分だ。

$4$ の倍数: $m, n$ は偶奇が異なるので $mn$ は偶数。よって $y = 2 mn$ は $4$ の倍数。
$3$ の倍数: $m, n$ とも $3$ で割れないなら $m^{2} \equiv n^{2} \equiv 1$ で、 $x = m^{2} - n^{2} \equiv 0$ 。
$5$ の倍数: $m, n$ とも $5$ で割れないなら $m^{2}, n^{2} \in {1, 4}$ 。同じ値なら $x \equiv 0$ 、違う値なら $z = m^{2} + n^{2} \equiv 1 + 4 \equiv 0$ 。

どの素因数も $x, y, z$ の誰かが必ず担う。本解のもどかしい $4$ の議論も、一般形の上では「 $mn$ が偶数」の一言に整理される。

ポイント

$60 = 4 \cdot 3 \cdot 5$ 、各素因数で割り切れることを別々に示す。
平方数の $mod 3, 4, 5$ の取りうる値が限られる。
$x^{2} + y^{2} = z^{2}$ に当てはめ、どれかが割り切れると背理法で示す。

よくある間違い

平方数の余りの表( $mod 3$ で ${0, 1}$ など)を確認せずに使う( $0^{2}, 1^{2}, 2^{2}$ を割ってみるだけの数行を惜しまない)。
$4$ の段で「 $x, y$ の一方が偶数」まで示して満足する(積に因数 $2$ が $1$ 個では足りない。その偶数が実は $4$ の倍数であることまで詰める)。
$5$ の段で $z$ を候補から外す( $3$ や $4$ と違い、 $5$ は $z$ が担うことがある。例: $3, 4, 5$ では $z = 5$ )。

問6オイラー関数の値(互いに素な数の個数)

実戦編整数の性質オイラー関数包除原理数え上げ単元横断

問題

$360$ 以下の自然数のうち、 $360$ と互いに素なものの個数 $φ (360)$ を求めよ。

ヒントを見る

$360 = 2^{3} \cdot 3^{2} \cdot 5$ 。互いに素 $=$ $2, 3, 5$ のどれでも割り切れない。包除原理で数えるか、公式 $φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})$ を使う。

解答・解説

方針

$360$ の素因数は $2, 3, 5$ 。 $2, 3, 5$ のいずれでも割り切れない数を包除原理で数える。これは $360 \prod (1 - \frac{1}{p})$ に等しい。

解答

⓪ 発想(どう考え始めるか) $360$ と互いに素とは、 $360$ の素因数 $2, 3, 5$ のどれでも割り切れないことだ。

だから数えるべきは「 $2$ でも $3$ でも $5$ でも割り切れない数」。裏返して、 $2$ または $3$ または $5$ で割り切れる数を包除原理で数え、全体 $360$ から引けばよい。

この計算を整理すると、素因数 $p$ ごとに「割り切れない割合 $1 - \frac{1}{p}$ 」を掛ける形にまとまる。 $φ (n) = n p ∣ n \prod (1 - \frac{1}{p})$ という積の公式だ。

定理オイラー関数

φ (n) = n p ∣ n \prod (1 - \frac{1}{p})

(

p

は

n

の相異なる素因数)

① 素因数分解。 $360 = 2^{3} \cdot 3^{2} \cdot 5$ 。相異なる素因数は $2, 3, 5$ 。

② 公式にあてはめる。 $φ (360) = 360 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} .$ ③ 計算する。 順に $360 \cdot \frac{1}{2} = 180$ 、 $180 \cdot \frac{2}{3} = 120$ 、 $120 \cdot \frac{4}{5} = 96$ 。よって $φ (360) = 96.$ (包除でも: $360 - (180 + 120 + 72) + (60 + 36 + 24) - 12 = 96$ 。)

まとめ互いに素 $=$ 素因数 $2, 3, 5$ で割り切れない。包除原理を整理した公式 $φ (n) = n \prod (1 - \frac{1}{p})$ で $360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96$ 。整数(オイラー関数)と数え上げの融合。

発展。 $φ$ には、 $m, n$ が互いに素なら $φ (mn) = φ (m) φ (n)$ という乗法性があり、 $φ (360) = φ (8) φ (9) φ (5) = 4 \cdot 6 \cdot 4 = 96$ とも計算できる。さらに約数全体で足すと $\sum_{d ∣ n} φ (d) = n$ という等式が成り立つ(分数 $\frac{1}{n}, \dots, \frac{n}{n}$ を約分して分母で仕分けると分かる)。

答

$360 = 2^{3} \cdot 3^{2} \cdot 5$ 。包除原理(または積の公式)で $φ (360) = 360 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 96$ 。

別解

別解: $30$ ごとの繰り返しで数える(苦手な人向け)。 $360$ と互いに素かどうかは、 $2, 3, 5$ で割り切れるかだけで決まる。そしてこの割り切れ方は $30 = 2 \cdot 3 \cdot 5$ ごとに同じパターンを繰り返す。

まず $1 \sim 30$ で、 $2, 3, 5$ のどれでも割り切れない数を書き出す。

$1, 7, 11, 13, 17, 19, 23, 29 の 8 個 .$

$360 = 30 \times 12$ だから、このパターンが $12$ 回繰り返される。 $8 \times 12 = 96$ 。包除原理の式を経由しなくても、周期性と手の数え上げだけで同じ $96$ に届く。素因数が小さいときは、この「 $1$ 周期だけ数える」方法が確実で速い。

ポイント

互いに素 $=$ 素因数 $2, 3, 5$ のどれでも割り切れない。
包除原理を整理すると $φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})$ 。
$360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96$ 。

よくある間違い

包除で $3$ 重の重なり( $30$ の倍数)を足し戻し忘れる。
積の公式の $p$ に素因数のべき( $8, 9, 5$ )を入れて $(1 - \frac{1}{8})$ などとする( $p$ は素因数そのもの $2, 3, 5$ )。
「互いに素」を「どちらかが素数」と混同する( $49$ は素数でないが $360$ と互いに素。共通の素因数がない、が定義)。

問7連続する和が n の倍数(鳩の巣原理)

実戦編整数の性質鳩の巣原理合同数え上げ単元横断

問題

$n$ 個の整数 $a_{1}, a_{2}, \dots, a_{n}$ が与えられたとき、連続して並ぶいくつかの和 $a_{i + 1} + a_{i + 2} + \dots + a_{j}$ ( $0 \leq i < j \leq n$ )で $n$ の倍数になるものが必ず存在することを示せ。

ヒントを見る

部分和 $S_{k} = a_{1} + \dots + a_{k}$ ( $S_{0} = 0$ )を $n + 1$ 個作る。 $n$ で割った余りは $n$ 種類。 $n + 1$ 個を $n$ 個の箱に入れると?

解答・解説

方針

$n + 1$ 個の部分和 $S_{0}, S_{1}, \dots, S_{n}$ を $n$ で割った余りで分類する。余りは $n$ 種類しかないので、鳩の巣原理で同じ余りの2つが存在し、その差が求める連続和。

解答

⓪ 発想(どう考え始めるか) 連続和 $a_{i + 1} + \dots + a_{j}$ は、部分和の差 $S_{j} - S_{i}$ で書ける( $S_{k} = a_{1} + \dots + a_{k}$ 、 $S_{0} = 0$ )。

だから「連続和が $n$ の倍数」は「 $S_{i} \equiv S_{j} (mod n)$ となる $2$ つがある」と同じことだ。部分和は $S_{0}, S_{1}, \dots, S_{n}$ の $n + 1$ 個。 $n$ で割った余りは $n$ 種類しかない。 $n + 1$ 個を $n$ 個の箱に入れるのだから、鳩の巣原理で同じ箱に入る $2$ つが必ずある。

定理鳩の巣原理:

n + 1

個のものを

n

個の箱に入れると、

2

つ以上入る箱が必ずある

① 部分和を作る。 $S_{0} = 0, S_{k} = a_{1} + a_{2} + \dots + a_{k}$ ( $k = 1, \dots, n$ )とすると、これは $n + 1$ 個。連続和は差で $a_{i + 1} + a_{i + 2} + \dots + a_{j} = S_{j} - S_{i} .$ ② 余りで分類。 $S_{0}, \dots, S_{n}$ を $n$ で割った余りは $0, 1, \dots, n - 1$ の $n$ 種類。 $n + 1$ 個の部分和を $n$ 個の余りに分けると、鳩の巣原理で同じ余りをもつ $2$ つ $S_{i}, S_{j}$ ( $i < j$ )が存在する。

③ 差が $n$ の倍数。 $S_{i} \equiv S_{j} (mod n)$ だから $S_{j} - S_{i}$ は $n$ の倍数。すなわち $a_{i + 1} + a_{i + 2} + \dots + a_{j} = S_{j} - S_{i}$ が $n$ の倍数。これで存在が示せた。

まとめ連続和を部分和の差とみて、 $n + 1$ 個の部分和を余り( $n$ 種類)で分類。鳩の巣原理で同じ余りの $2$ つがあり、その差の連続和が $n$ の倍数。整数(合同)と鳩の巣原理の融合。

発展。 「連続」を外して「自由に選ぶ」と、話は急に深くなる。任意の $2 n - 1$ 個の整数からは、和が $n$ の倍数になる $n$ 個を必ず選べる(エルデシュ・ギンツブルク・ジヴの定理)。しかも $2 n - 2$ 個では足りない( $0$ を $n - 1$ 個と $1$ を $n - 1$ 個の例)。鳩の巣原理よりずっと難しい内容だ。

答

部分和 $S_{0} = 0, S_{k} = a_{1} + \dots + a_{k}$ の $n + 1$ 個を $n$ で割った余りで分類。余りは $n$ 種類だから鳩の巣原理で $S_{i} \equiv S_{j}$ となる組があり、 $S_{j} - S_{i} = a_{i + 1} + \dots + a_{j}$ が $n$ の倍数。

別解

別解:小さな例で鳩の巣を「見る」(苦手な人向け)。 $n = 5$ 、数を $3, 7, 2, 8, 4$ としてみる。部分和は

$S_{0} = 0, S_{1} = 3, S_{2} = 10, S_{3} = 12, S_{4} = 20, S_{5} = 24.$

$5$ で割った余りは順に $0, 3, 0, 2, 0, 4$ 。 $6$ 個の部分和に余りは $5$ 種類しかないから、必ずどこかがかぶる。ここでは $S_{0}$ と $S_{2}$ (どちらも余り $0$ )。

差をとると $S_{2} - S_{0} = a_{1} + a_{2} = 3 + 7 = 10$ 。たしかに $5$ の倍数の連続和が見つかった。 $S_{0} = 0$ を仲間に入れておくのがポイントだ。 $S_{0}$ とかぶった場合は「先頭からの連続和」が答えになる。証明の一行一行がこの小さな実験の一般化になっている。

ポイント

連続和は部分和の差 $S_{j} - S_{i}$ 。
部分和は $S_{0}, \dots, S_{n}$ の $n + 1$ 個、余りは $n$ 種類。
鳩の巣原理で $S_{i} \equiv S_{j}$ 、差が $n$ の倍数。

よくある間違い

$S_{0} = 0$ を仲間に入れ忘れ、部分和が $n$ 個になって鳩の巣が発動しない( $n + 1$ 個そろえるのが命)。
「連続して並ぶ」を「好きに選んでよい」と読み違える(選んでよいとすると、難しさがまるで違う別問題になる)。
余りの種類を $n + 1$ 種と数える( $0$ から $n - 1$ の $n$ 種類。個数 $n + 1$ との差の $1$ が鳩の巣を生む)。

問8素数を法とする二項展開(フロベニウスの夢)

実戦編整数の性質二項定理合同素数単元横断

問題

$p$ を素数とする。(1) $0 < k < p$ のとき二項係数 $(k p)$ は $p$ の倍数であることを示せ。

(2) すべての整数 $a, b$ について $(a + b)^{p} \equiv a^{p} + b^{p} (mod p)$ を示せ。

ヒントを見る

(1) $(k p) = \frac{p}{k} (k - 1 p - 1)$ を整数の等式 $k (k p) = p (k - 1 p - 1)$ に。 $p$ 素数、 $0 < k < p$ なら $p$ と $k$ は互いに素。(2) 二項展開の中間項が(1)で消える。

解答・解説

方針

(1) 等式 $k (k p) = p (k - 1 p - 1)$ を使い、 $p$ が素数で $0 < k < p$ なら $p ∤ k$ から $(k p)$ が $p$ の倍数。(2) それを二項定理に入れて中間項を消す。

解答

⓪ 発想(どう考え始めるか) (1) の決め手は整数の等式 $k (k p) = p (k - 1 p - 1)$ だ。右辺は見るからに $p$ の倍数だ。

左辺を見る。 $p$ は素数で $0 < k < p$ だから、 $k$ は $p$ と互いに素。すると $p$ は $k$ の側を割れないので、 $(k p)$ の側を割るしかない。

(2) はこの事実の収穫だ。 $(a + b)^{p}$ を二項定理で開くと、中間項( $0 < k < p$ )が $mod p$ で全部消え、両端の $a^{p} + b^{p}$ だけが残る。「和の $p$ 乗がバラバラに乗る」。素数だけで起こる現象である。

重要整数の等式

k (k p) = p (k - 1 p - 1)

① $(k p)$ が $p$ の倍数。 上の等式で右辺は $p$ の倍数だから、左辺 $k (k p)$ も $p$ の倍数。 $p$ は素数で $0 < k < p$ より $p ∤ k$ 、すなわち $p$ と $k$ は互いに素。よって $p$ は $(k p)$ を割る(素数が積を割るとき、互いに素でない方を割る)。ゆえに $0 < k < p$ で $(k p) \equiv 0 (mod p)$ 。

② 二項展開の中間項が消える。 二項定理から $(a + b)^{p} = k = 0 \sum p (k p) a^{p - k} b^{k} = a^{p} + 各 (k p) \equiv 0 k = 1 \sum p - 1 (k p) a^{p - k} b^{k} + b^{p} .$ 中間の和は各係数 $(k p) (0 < k < p)$ が $p$ の倍数だから $mod p$ で $0$ 。よって $(a + b)^{p} \equiv a^{p} + b^{p} (mod p) .$

まとめ $k (k p) = p (k - 1 p - 1)$ と $p ∤ k$ から $(k p) \equiv 0 (0 < k < p)$ 。二項定理の中間項が消えて $(a + b)^{p} \equiv a^{p} + b^{p}$ 。これはフェルマーの小定理の基礎でもある。整数・二項定理・素数の融合。

発展。 (2) を繰り返すと $(a_{1} + \dots + a_{m})^{p} \equiv a_{1}^{p} + \dots + a_{m}^{p}$ 。とくに $1$ を $a$ 個足した式に使えば $a^{p} \equiv a$ 、フェルマーの小定理が一行で出る。この単元の帰納法による証明と根は同じ( $1$ ずつ足す)ながら、見方の違う方法である。

答

(1) $k (k p) = p (k - 1 p - 1)$ の右辺が $p$ の倍数で、 $0 < k < p$ より $k$ は $p$ と互いに素だから $(k p)$ が $p$ の倍数。(2) 二項定理の中間項が $mod p$ で消えて $(a + b)^{p} \equiv a^{p} + b^{p}$ 。

別解

別解:円卓の回転で示す(得意な人向けの高い視点)。 $(k p)$ を「円周上に等間隔に並んだ $p$ 個の席から $k$ 席を選ぶ場合の数」と読み替える。

選び方全体を、円の回転( $1$ 席ずつずらす)で仲間分けする。 $1$ つの選び方は $p$ 回の回転で元に戻るから、各グループの大きさは $p$ の約数。 $p$ は素数なので、大きさは $1$ か $p$ しかない。

大きさ $1$ のグループとは「どの回転でも変わらない選び方」。それは全席選ぶ( $k = p$ )か何も選ばない( $k = 0$ )だけで、 $0 < k < p$ ではあり得ない。よってすべてのグループの大きさはちょうど $p$ 。総数 $(k p)$ は大きさ $p$ のグループの寄せ集めだから、 $p$ の倍数である。

数式の割り算(本解)を使わず、「素数個の回転は途中で戻れない」という対称性だけで示せた。この「回転で仲間分け」は円順列など数え上げの証明で繰り返し現れる有効な見方だ。

ポイント

$k (k p) = p (k - 1 p - 1)$ と $p ∤ k (0 < k < p)$ から $(k p) \equiv 0$ 。
二項定理の中間項が $mod p$ で消える。
$(a + b)^{p} \equiv a^{p} + b^{p} (mod p)$ 。

よくある間違い

(1) を「分子 $p!$ に $p$ があるから」で済ませる(分母との約分で消えない理由=分母の因数はすべて $p$ 未満、が本体)。
素数の仮定を落とし、一般の $n$ でも $(k n)$ が $n$ の倍数だと思い込む( $(2 4) = 6$ は $4$ の倍数でない)。
(2) で両端の項 $k = 0, p$ まで消してしまう(消えるのは中間項だけ。残る $a^{p} + b^{p}$ が結論そのもの)。

整数の性質 実戦編の問題 全8問

問1100! の末尾に並ぶ0の個数(素因数の個数)

問題

方針

解答

別解

ポイント

よくある間違い

問2フェルマーの小定理(二項定理と帰納法)

問題

方針

解答

別解

ポイント

よくある間違い

問33の2024乗を100で割った余り(位数)

問題

方針

解答

別解

ポイント

よくある間違い

問4(2+√3)ⁿ の整数部分は奇数(共役と漸化式)

問題

方針

解答

別解

ポイント

よくある間違い

問5ピタゴラス数の積は60の倍数(合同で場合分け)

問題

方針

解答

別解

ポイント

よくある間違い

問6オイラー関数の値(互いに素な数の個数)

問題

方針

解答

別解

ポイント

よくある間違い

問7連続する和が n の倍数(鳩の巣原理)

問題

方針

解答

別解

ポイント

よくある間違い

問8素数を法とする二項展開(フロベニウスの夢)

問題

方針

解答

別解

ポイント

よくある間違い

整数の性質実戦編の問題全8問