累乗の余りの周期

$2^{n} (mod 15)$ などの余りが周期的にくり返すことを見つけ、 $2^{n} + n^{3}$ のように周期の異なる項の和では最小公倍数を周期として、範囲内の個数を数えられる

前提

合同式（数学A 整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）

この技能までの道筋（20 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）

説明

$2^{n}$ を $15$ で割った余りのように、累乗を割った余りは $n$ を増やしていくと、ある位置から先は同じ並びをくり返します。このくり返しの長さ（周期）と、くり返しが始まる位置を見つければ、 $n$ がどんなに大きくても余りがすぐにわかります。さらに $2^{n} + n^{3}$ のように周期の違う項の和でも、2 つの周期の最小公倍数を 1 つの区切りとして表を作れば、「 $1 \leq n \leq 100$ で条件を満たす $n$ の個数」などを数えられます。

なぜそうしてよいのか

たとえば $2^{4} = 16 \equiv 1 (mod 15)$ です。合同式の積の性質から $2^{n + 4} = 2^{n} \cdot 2^{4} \equiv 2^{n} (mod 15)$ となるので、余りは $2, 4, 8, 1, 2, 4, 8, 1, \dots$ と $n = 1$ から $4$ 個ずつくり返します。一般に $m$ で割った余りは $0$ から $m - 1$ の有限個しかないので、計算を続ければいつか前に出た余りがもう一度現れます。しかも次の余りは「今の余りに $a$ を掛けて $m$ で割った余り」だけで決まるので、 $n = i$ と $n = j (i < j)$ で余りが一致すれば、 $n = i$ から先は長さ $j - i$ で同じ並びをくり返します。

このとき 2 つの場合があります。最初の余り（ $n = 1$ の余り）に戻るなら、くり返しは $n = 1$ から始まります。途中の余りに戻るなら、くり返しは途中から始まり、その前の部分は一度しか現れません。たとえば $2^{n} (mod 12)$ は $2, 4, 8, 4, 8, \dots$ で、 $2$ には二度と戻らず、 $n = 2$ から周期 $2$ でくり返します。 $a$ と $m$ が互いに素（共通の素因数をもたない）なら必ず前者になります。実際 $a^{i} \equiv a^{j} (i < j)$ なら $m$ は $a^{i} (a^{j - i} - 1)$ を割り切りますが、 $a^{i}$ は $m$ と共通の素因数をもたないので、 $m$ は $a^{j - i} - 1$ を割り切り、 $a^{j - i} \equiv 1 (mod m)$ となるからです。

一方 $n^{k}$ のような項は、 $n + m \equiv n (mod m)$ と累乗の性質から $(n + m)^{k} \equiv n^{k} (mod m)$ なので、 $n = 1$ から周期 $m$ でくり返します。周期 $p$ の項と周期 $q$ の項の和では、 $n$ を増やす量が $p$ の倍数でも $q$ の倍数でもあれば両方が同時に元に戻ります。その最小の数が最小公倍数 $L$ なので、和の余りは（両方がくり返しに入った位置から先で）周期 $L$ でくり返し、 $L$ 個だけ調べれば残りは同じことのくり返しとして数えられます。

手順

累乗の項 $a^{n}$ を $m$ で割った余りを $n = 1, 2, 3, \dots$ と順に計算し、前に出た余りが再び現れるところを見つける。 $n = t$ の余りが $n = t + p$ で初めて再び現れたら、くり返しは $n = t$ から始まり周期は $p$ （ $a$ と $m$ が互いに素なら $a^{p} \equiv 1 (mod m)$ となる $p$ があり $t = 1$ 。互いに素でないときは $1$ に戻らないことがある。例： $2^{n} (mod 12)$ は $t = 2, p = 2$ ）。
$n^{k}$ のような項は $(n + m)^{k} \equiv n^{k} (mod m)$ なので $n = 1$ から周期 $m$ として、 $n = 1, \dots, m$ の余りを書き出す。
2 つの周期の最小公倍数 $L$ を求め、くり返しが始まる $n = t$ から $n = t + L - 1$ までの $L$ 個について和の余りの表を作る。 $t \geq 2$ なら、くり返しに入らない $n = 1, \dots, t - 1$ は別に直接計算しておく。
表から 1 周期の中で条件を満たす $n$ の個数 $c$ を数える。
$n = t$ から上限 $N$ までの個数 $N - t + 1$ を $N - t + 1 = L q + r (0 \leq r < L)$ と表し、個数を「 $c \times q$ ＋（表の最初の $r$ 個のうち条件を満たす個数）＋（ $n = 1, \dots, t - 1$ で条件を満たす個数）」として求める（ $t = 1$ なら最後の項はなく、 $N = L q + r$ ）。

例題

$1 \leq n \leq 100$ を満たす整数 $n$ のうち、 $2^{n} + n^{2}$ が $3$ で割り切れるものの個数を求めよ。

例題の解答

手順1： $2^{1} \equiv 2, 2^{2} = 4 \equiv 1 (mod 3)$ 。 $2$ と $3$ は互いに素で、 $2^{2} \equiv 1$ となるので、 $2^{n}$ の余りは $n = 1$ から $2, 1, 2, 1, \dots$ と周期 $2$ でくり返す（ $t = 1$ 。 $n$ が奇数なら $2$ 、偶数なら $1$ ）。

手順2： $n^{2}$ を $3$ で割った余りは $n = 1$ から周期 $3$ 。 $n = 1, 2, 3$ で $1, 1, 0$ 。

手順3： $2$ と $3$ の最小公倍数は $L = 6$ 。どちらも $n = 1$ からくり返すので、前に別扱いする部分はなく、 $n = 1, \dots, 6$ の表を作る。
$n = 1$ ： $2 + 1 = 3 \equiv 0$
$n = 2$ ： $1 + 1 = 2$
$n = 3$ ： $2 + 0 = 2$
$n = 4$ ： $1 + 1 = 2$
$n = 5$ ： $2 + 1 = 3 \equiv 0$
$n = 6$ ： $1 + 0 = 1$

手順4：1 周期（6 個）の中で割り切れるのは $n = 1, 5$ の $c = 2$ 個。つまり $n$ を $6$ で割った余りが $1$ または $5$ のとき。

手順5： $t = 1$ なので $100 = 6 \times 16 + 4$ 。 $1 \leq n \leq 96$ の 16 周期分で $2 \times 16 = 32$ 個。残りの $n = 97, 98, 99, 100$ は表の $n = 1, 2, 3, 4$ と同じ余りになり、このうち条件を満たすのは $n = 97$ （表の $n = 1$ に対応）の 1 個。

よって $32 + 1 = 33$ 個。

答え: $33$

よくある誤り

2 つの周期のうち大きいほうを全体の周期としてしまう誤り。例では $2^{n}$ が周期 $2$ 、 $n^{2}$ が周期 $3$ なので周期 $3$ としがちだが、 $n = 1$ と $n = 4$ で和の余りは $0$ と $2$ で異なる。正しくは最小公倍数 $L = 6$ を周期とする。
周期の切れ目の余りを数え忘れる誤り。 $100 \div 6$ の商 $16$ だけ使って $2 \times 16 = 32$ 個としてしまう。正しくは $100 = 6 \times 16 + 4$ の余りの $4$ 個（ $n = 97, \dots, 100$ ）も調べ、 $n = 97$ を加えて $33$ 個。
どの累乗でも $n = 1$ から周期的になる、または必ず $a^{p} \equiv 1$ となる $p$ があると思い込む誤り。 $2^{n} (mod 12)$ は $2, 4, 8, 4, 8, \dots$ で、 $2$ と $12$ は互いに素でないため $2^{n} \equiv 1 (mod 12)$ となる $n$ はない。これを $n = 1$ から周期 $2$ （ $2, 4, 2, 4, \dots$ ）と扱うと $n = 3$ の余りを $2$ と誤る。正しくは $n = 2$ から周期 $2$ とし、 $n = 1$ は別に数える。
$n^{2}$ や $n^{3}$ の余りの周期を累乗の項と同じだと思い込む誤り。 $n^{2} (mod 3)$ を $2^{n}$ と同じ周期 $2$ と考えると $n = 3$ で余り $0$ になることを見落とす。正しくは $(n + 3)^{2} \equiv n^{2} (mod 3)$ より周期は $3$ で、 $n = 1, 2, 3$ の $1, 1, 0$ を調べる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

2 つの数列の共通項（数学B 数列）