高校数学Aでは、整数を $n$ で割った余りで分類する方法を学び、$\mathrm{mod}$ の記法にも触れます。
不定方程式を解くときにも「$\mathrm{mod}$ で考える」テクニックが登場します。
しかし高校では、余りの分類は問題を解くための道具にとどまり、余りの世界そのものの構造には踏み込みません。
大学数学では、「$a$ を $n$ で割った余りが等しい」という関係を合同式として定式化し、
合同式の中で足し算・引き算・掛け算が自由にできること、さらに条件を満たせば割り算もできることを示します。
この枠組みからフェルマーの小定理が導かれ、その応用としてRSA暗号の原理が説明できます。
余りという身近な概念の中に、現代暗号技術の数学的基盤があるのです。
高校数学Aの「整数の性質」では、整数を割り算の余りで分類する方法を学びます。 たとえば、すべての整数は $3$ で割った余りによって、$3k$, $3k+1$, $3k+2$（$k$ は整数）の3つのグループに分けられます。 「$n^2$ を $3$ で割った余りを求めよ」のような問題では、$n$ を $3$ で割った余りで場合分けして解きます。
この分類を簡潔に表す記法として $\mathrm{mod}$ が登場します。 「$a$ を $n$ で割った余りが $r$ である」ことを $a \equiv r \pmod{n}$ と書きます。 たとえば $17 \equiv 2 \pmod{5}$ は「$17$ を $5$ で割った余りは $2$」という意味です。
また、不定方程式の問題でも $\mathrm{mod}$ は活躍します。 たとえば $3x + 5y = 1$ の整数解を求める際、両辺を $\mathrm{mod}\;3$ で考えると $5y \equiv 1 \pmod{3}$、すなわち $2y \equiv 1 \pmod{3}$ となり、$y \equiv 2 \pmod{3}$ が得られます。 ここから $y = 3t + 2$（$t$ は整数）と表して $x$ を求める、という手法です。
高校ではこのように、$\mathrm{mod}$ は「余りに注目して問題を解くテクニック」として使われます。 しかし、「余りの世界で足し算や掛け算ができるのはなぜか」「割り算はいつできるのか」という構造的な問いには踏み込みません。 次のセクションでは、大学の視点がこれらの問いにどう答えるかを見ます。
大学の整数論では、$\mathrm{mod}\;n$ による分類を合同関係（congruence relation）として厳密に定義します。 そして、余りの世界の中で加法・減法・乗法が矛盾なく定義でき、さらに条件を満たせば除法（逆元による乗法）も可能であることを証明します。 つまり、余りの集合 $\{0, 1, 2, \ldots, n-1\}$ は単なる分類ではなく、演算が定義された代数系です。
この記事を読み終えると、以下のことができるようになります。
1. 合同式の加法・減法・乗法が保存される理由を証明できる
2. $\gcd(a, n) = 1$ のとき、$a$ の $\mathrm{mod}\;n$ における逆元が存在することを説明できる
3. フェルマーの小定理を述べ、証明できる
4. RSA暗号の鍵生成・暗号化・復号の仕組みを、小さな数の例で実演できる
5. 合同式を使って、高校レベルの整数問題をより見通しよく解ける
これらの能力を得るには、まず合同式の演算規則を正確に把握する必要があります。 次のセクションでは、合同式の定義から始めて、四則演算の規則を一つずつ確認します。
まず、合同式を厳密に定義します。
整数 $a, b$ と正の整数 $n$ に対して、$a - b$ が $n$ で割り切れるとき、$a$ と $b$ は $n$ を法として合同であるといい、次のように書きます。
$$a \equiv b \pmod{n}$$
これは「$n \mid (a - b)$」（$n$ は $a - b$ を割り切る）と同じ意味です。
なぜこう定義するのか：「$a$ を $n$ で割った余り」と「$b$ を $n$ で割った余り」が等しいことと、「$a - b$ が $n$ で割り切れる」ことは同値です。差で定義するほうが、余りの概念に頼らず、演算規則の証明が簡潔になります。
具体例で確認します。$17 \equiv 2 \pmod{5}$ は $17 - 2 = 15 = 5 \times 3$ なので正しいです。 同様に $-3 \equiv 4 \pmod{7}$ は $-3 - 4 = -7 = 7 \times (-1)$ なので正しいです。 負の数でも合同式は成り立ちます。
合同式の最も重要な性質は、両辺に同じ演算を施しても合同関係が保たれることです。 高校では「$\mathrm{mod}$ の計算で足し算や掛け算をしてよい」と暗黙に使っていますが、大学ではこれを定理として証明します。
$a \equiv b \pmod{n}$ かつ $c \equiv d \pmod{n}$ のとき、以下が成り立ちます。
加法： $a + c \equiv b + d \pmod{n}$
減法： $a - c \equiv b - d \pmod{n}$
乗法： $a \cdot c \equiv b \cdot d \pmod{n}$
特に、乗法を繰り返すと累乗も保存されます。$a \equiv b \pmod{n}$ ならば、任意の正の整数 $k$ に対して $a^k \equiv b^k \pmod{n}$ が成り立ちます。
示すこと： $a \equiv b \pmod{n}$ かつ $c \equiv d \pmod{n}$ ならば $ac \equiv bd \pmod{n}$。
仮定より、$a - b = nk$, $c - d = nl$（$k, l$ は整数）と書けます。つまり $a = b + nk$, $c = d + nl$ です。
$ac$ を計算します。
$$ac = (b + nk)(d + nl) = bd + bnl + nkd + n^2kl = bd + n(bl + kd + nkl)$$
$bl + kd + nkl$ は整数なので、$ac - bd$ は $n$ の倍数です。
したがって $ac \equiv bd \pmod{n}$ が成り立ちます。$\square$
この証明は、加法・減法についても同様に（より簡単に）示せます。 加法については $a - b = nk$, $c - d = nl$ から $(a+c)-(b+d) = n(k+l)$ が直ちに得られます。
乗法の保存は強力です。たとえば、$3 \equiv -1 \pmod{4}$ なので、$3^{10} \equiv (-1)^{10} = 1 \pmod{4}$ と分かります。 $3^{10} = 59049$ を直接 $4$ で割る必要がありません。
加法・減法・乗法はいつでも保存されますが、除法は常にできるわけではありません。 これが合同式で最も注意すべき点です。
誤： $6 \equiv 0 \pmod{6}$ の両辺を $2$ で割って $3 \equiv 0 \pmod{6}$。
$3 - 0 = 3$ は $6$ の倍数ではないので、これは誤りです。
正： $ac \equiv bc \pmod{n}$ から $a \equiv b \pmod{n}$ が言えるのは、$\gcd(c, n) = 1$ のときだけです。
上の例では $\gcd(2, 6) = 2 \neq 1$ なので割れません。正しくは $6 \equiv 0 \pmod{6}$ の両辺を $2$ で割ると $3 \equiv 0 \pmod{3}$ となります（法も $2$ で割る）。
では、割り算（逆元の存在）が保証される条件を正確に述べます。
整数 $a$ と正の整数 $n$ に対して、$ax \equiv 1 \pmod{n}$ を満たす整数 $x$ が存在するための必要十分条件は、
$$\gcd(a, n) = 1$$
です。この $x$ を $a$ の $\mathrm{mod}\;n$ における逆元といい、$a^{-1}$ と書きます。
なぜ成り立つか：$ax \equiv 1 \pmod{n}$ は $ax - 1 = ny$、すなわち $ax - ny = 1$ と同じです。これは $a$ と $n$ の一次不定方程式であり、高校で学んだように、整数解が存在する条件は $\gcd(a, n) \mid 1$、すなわち $\gcd(a, n) = 1$ です。
具体例を見ます。$\mathrm{mod}\;7$ における $3$ の逆元を求めます。$3x \equiv 1 \pmod{7}$ を満たす $x$ を探すと、$3 \times 5 = 15 = 2 \times 7 + 1$ なので $3 \times 5 \equiv 1 \pmod{7}$ です。 したがって $3^{-1} \equiv 5 \pmod{7}$ です。
逆元はユークリッドの互除法（高校で学習済み）を使って組織的に計算できます。 $\gcd(a, n) = 1$ のとき、互除法の逆算で $ax + ny = 1$ の整数解 $(x, y)$ が見つかり、その $x$ が逆元です。
ここまでで、合同式の四則演算の規則が整理できました。 加法・減法・乗法は常に保存され、除法（逆元）は $\gcd(a, n) = 1$ のときに可能です。 特に $n$ が素数 $p$ のとき、$0$ 以外のすべての整数 $a$（$1 \leq a \leq p-1$）が $\gcd(a, p) = 1$ を満たすため、自由に割り算ができます。 この性質が、次のセクションで証明するフェルマーの小定理の鍵になります。
セクション3で、$p$ が素数のとき $1, 2, \ldots, p-1$ のすべてが $\mathrm{mod}\;p$ で逆元を持つことを確認しました。 この事実から、合同式における累乗計算に関する非常に強力な定理が導かれます。
$p$ を素数、$a$ を $p$ の倍数でない整数とするとき、
$$a^{p-1} \equiv 1 \pmod{p}$$
が成り立ちます。同値な表現として、任意の整数 $a$ に対して $a^p \equiv a \pmod{p}$ が成り立ちます。
この定理の意味：$p$ が素数なら、$p$ と互いに素な任意の整数を $p-1$ 乗すると、$\mathrm{mod}\;p$ で必ず $1$ になります。指数が何であっても、$p-1$ で割った余りだけ考えればよいのです。
証明の前に、具体例で定理を確認しておきます。
例1： $p = 5$, $a = 2$ のとき、$a^{p-1} = 2^4 = 16 = 3 \times 5 + 1$ なので $2^4 \equiv 1 \pmod{5}$ です。
例2： $p = 7$, $a = 3$ のとき、$a^{p-1} = 3^6 = 729 = 104 \times 7 + 1$ なので $3^6 \equiv 1 \pmod{7}$ です。
例3（応用）： $7^{100}$ を $5$ で割った余りを求めます。$\gcd(7, 5) = 1$ なので、フェルマーの小定理より $7^4 \equiv 1 \pmod{5}$ です。$100 = 4 \times 25$ なので、$7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{5}$ です。高校で周期性を調べて解く問題が、定理一つで解決します。
証明の方針： $1, 2, \ldots, p-1$ の各要素に $a$ を掛けた $a, 2a, 3a, \ldots, (p-1)a$ が、$\mathrm{mod}\;p$ で $1, 2, \ldots, p-1$ の並べ替えになっていることを示します。両方の積を取って比較すると、定理が得られます。
ステップ1： $a, 2a, 3a, \ldots, (p-1)a$ が $\mathrm{mod}\;p$ ですべて異なることを示します。
もし $ia \equiv ja \pmod{p}$（$1 \leq i, j \leq p-1$, $i \neq j$）とすると、$(i - j)a \equiv 0 \pmod{p}$ です。$p$ は素数で $a$ は $p$ の倍数でないので、$\gcd(a, p) = 1$ です。セクション3の逆元の存在より両辺に $a^{-1}$ を掛けると $i - j \equiv 0 \pmod{p}$ ですが、$|i - j| < p$ なので $i = j$ となり矛盾します。よって $a, 2a, \ldots, (p-1)a$ は $\mathrm{mod}\;p$ ですべて異なります。
ステップ2： これらは $\mathrm{mod}\;p$ で $0$ にならないことを示します。
$ia \equiv 0 \pmod{p}$ とすると $p \mid ia$ ですが、$p$ は素数で $\gcd(a, p) = 1$ なので $p \mid i$ です。$1 \leq i \leq p-1$ よりこれは不可能です。
ステップ3： ステップ1, 2より、$a, 2a, \ldots, (p-1)a$ の $\mathrm{mod}\;p$ での値は $\{1, 2, \ldots, p-1\}$ の並べ替えです（$p-1$ 個の互いに異なる要素で、いずれも $1$ 以上 $p-1$ 以下）。
ステップ4： 両方の積を取ります。
$$a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$$
左辺は $a^{p-1} \cdot (p-1)!$ です。したがって、
$$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$$
$(p-1)! = 1 \times 2 \times \cdots \times (p-1)$ の各因数はいずれも $p$ と互いに素なので、$\gcd((p-1)!, p) = 1$ です。セクション3の結果より $(p-1)!$ で割ることができて、
$$a^{p-1} \equiv 1 \pmod{p}$$
が得られます。$\square$
この証明のポイントは、セクション3で確認した2つの事実を使っていることです。 (1) 合同式の乗法の保存（ステップ4で積を取る際）、(2) $\gcd(a, p) = 1$ のとき逆元が存在し割り算ができること（ステップ1とステップ4で使用）。 つまり、フェルマーの小定理は合同式の演算規則の直接的な帰結です。
フェルマーの小定理は $n$ が素数の場合の結果ですが、一般の正整数 $n$ に対しても類似の定理があります。オイラーの定理は、$\gcd(a, n) = 1$ のとき $a^{\phi(n)} \equiv 1 \pmod{n}$ が成り立つことを主張します。ここで $\phi(n)$ はオイラーのトーシェント関数で、$1$ から $n$ までの整数のうち $n$ と互いに素なものの個数です。$n = p$（素数）のとき $\phi(p) = p - 1$ なので、フェルマーの小定理はオイラーの定理の特殊ケースです。次のセクションのRSA暗号では、このオイラーの定理が核心的な役割を果たします。
フェルマーの小定理は累乗計算を大幅に簡略化する道具ですが、その真価は暗号理論への応用にあります。 次のセクションでは、この定理（とその一般化であるオイラーの定理）を使って、RSA暗号の仕組みを実際に動かしてみます。
RSA暗号は1977年にRivest, Shamir, Adlemanの3人によって提案された公開鍵暗号の方式で、現在もインターネット上の通信で広く使われています。 その数学的原理は、ここまで学んできた合同式とフェルマーの小定理（の一般化であるオイラーの定理）です。
RSA暗号は、「暗号化する鍵」と「復号する鍵」が異なる非対称暗号です。 暗号化の鍵は公開し（公開鍵）、復号の鍵は秘密にします（秘密鍵）。 誰でも暗号化できるが、復号は鍵の持ち主しかできない、という仕組みです。
以下、手順を順に説明します。各ステップで合同式の性質がどう使われているかに注目してください。
公開鍵は $(n, e)$、秘密鍵は $d$ です。$p$, $q$, $\phi(n)$ は秘密にします。
平文（送りたいメッセージ）を整数 $m$（$0 \leq m < n$）に変換し、暗号文 $c$ を次の式で計算します。
$$c \equiv m^e \pmod{n}$$
これはセクション3で確認した合同式の累乗計算です。公開鍵 $(n, e)$ さえあれば、誰でも計算できます。
暗号文 $c$ を受け取った秘密鍵の持ち主は、次の計算を行います。
$$c^d \equiv (m^e)^d = m^{ed} \pmod{n}$$
ここが核心です。$ed \equiv 1 \pmod{\phi(n)}$ なので、$ed = 1 + k\phi(n)$（$k$ は整数）と書けます。
$$m^{ed} = m^{1 + k\phi(n)} = m \cdot (m^{\phi(n)})^k$$
$\gcd(m, n) = 1$ のとき、オイラーの定理（セクション4で紹介）より $m^{\phi(n)} \equiv 1 \pmod{n}$ なので、
$$m^{ed} \equiv m \cdot 1^k = m \pmod{n}$$
つまり、$c^d \equiv m \pmod{n}$ となり、元の平文 $m$ が復元されます。
RSA暗号が機能する理由は、オイラーの定理 $m^{\phi(n)} \equiv 1 \pmod{n}$ です。$ed \equiv 1 \pmod{\phi(n)}$ と組み合わせることで $m^{ed} \equiv m \pmod{n}$ が成り立ち、復号が可能になります。
安全性の根拠は、$n = pq$ から $p$, $q$ を求める（素因数分解する）ことが、$n$ が十分大きいとき計算量的に困難であることです。$\phi(n) = (p-1)(q-1)$ を知るには $p$, $q$ が必要なので、公開鍵 $(n, e)$ から秘密鍵 $d$ を計算することができません。
実際に小さな数で一連の手順を実行します。
鍵生成： $p = 5$, $q = 11$ とします。
公開鍵は $(55, 3)$、秘密鍵は $27$ です。
暗号化： 平文 $m = 7$ を暗号化します。
$$c \equiv 7^3 = 343 \equiv 343 - 6 \times 55 = 343 - 330 = 13 \pmod{55}$$
暗号文は $c = 13$ です。
復号： $c^d = 13^{27} \pmod{55}$ を計算します。直接計算すると大変なので、合同式の乗法の保存（セクション3）を使って段階的に計算します。
まず、$13^2 = 169 \equiv 169 - 3 \times 55 = 169 - 165 = 4 \pmod{55}$ です。
$13^4 \equiv 4^2 = 16 \pmod{55}$ です。
$13^8 \equiv 16^2 = 256 \equiv 256 - 4 \times 55 = 256 - 220 = 36 \pmod{55}$ です。
$13^{16} \equiv 36^2 = 1296 \equiv 1296 - 23 \times 55 = 1296 - 1265 = 31 \pmod{55}$ です。
$27 = 16 + 8 + 2 + 1$ なので、
$$13^{27} = 13^{16} \cdot 13^{8} \cdot 13^{2} \cdot 13^{1} \equiv 31 \times 36 \times 4 \times 13 \pmod{55}$$
順に計算します。$31 \times 36 = 1116 \equiv 1116 - 20 \times 55 = 1116 - 1100 = 16 \pmod{55}$。
$16 \times 4 = 64 \equiv 64 - 55 = 9 \pmod{55}$。
$9 \times 13 = 117 \equiv 117 - 2 \times 55 = 117 - 110 = 7 \pmod{55}$。
結果は $7$ で、元の平文 $m = 7$ が復元されました。合同式の演算規則とオイラーの定理が、暗号の復号を可能にしていることが確認できます。
ここまでで、合同式の理論がRSA暗号という実用的な応用につながることを見ました。 次のセクションでは視点を変えて、合同式を使って高校レベルの整数問題を解く例を見ます。 フェルマーの小定理や演算規則の保存が、問題解決の強力な道具になることを体感してください。
問題： $2^{100}$ を $7$ で割った余りを求めよ。
解法： $\gcd(2, 7) = 1$ なので、フェルマーの小定理より $2^6 \equiv 1 \pmod{7}$ です。 $100 = 6 \times 16 + 4$ なので、
$$2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 = 16 \equiv 2 \pmod{7}$$
答えは $2$ です。高校では $2^1, 2^2, 2^3, \ldots$ の余りを順に書き出して周期を探す方法を取りますが、フェルマーの小定理を使えば周期が $p - 1 = 6$ の約数であることが直ちに分かります。
問題： 任意の整数 $n$ に対して、$n^7 - n$ は $42$ で割り切れることを示せ。
解法： $42 = 2 \times 3 \times 7$ なので、$n^7 - n$ が $2$, $3$, $7$ のそれぞれで割り切れることを示せば十分です（$2$, $3$, $7$ は互いに素なので）。
フェルマーの小定理の第2形（$a^p \equiv a \pmod{p}$）を使います。
$2$, $3$, $7$ が互いに素で、いずれも $n^7 - n$ を割り切るので、$2 \times 3 \times 7 = 42$ も $n^7 - n$ を割り切ります。$\square$
問題： $3$ で割ると $2$ 余り、$5$ で割ると $3$ 余り、$7$ で割ると $4$ 余る正の整数のうち、最小のものを求めよ。
解法： 条件を合同式で書くと、
$$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 4 \pmod{7}$$
最初の条件から $x = 3k + 2$（$k$ は非負整数）です。これを第2の条件に代入します。
$$3k + 2 \equiv 3 \pmod{5} \implies 3k \equiv 1 \pmod{5}$$
$3$ の $\mathrm{mod}\;5$ における逆元は $2$ です（$3 \times 2 = 6 \equiv 1 \pmod{5}$）。両辺に $2$ を掛けて $k \equiv 2 \pmod{5}$、すなわち $k = 5l + 2$ です。
$x = 3(5l + 2) + 2 = 15l + 8$ です。これを第3の条件に代入します。
$$15l + 8 \equiv 4 \pmod{7} \implies 15l \equiv -4 \equiv 3 \pmod{7} \implies l \equiv 3 \pmod{7}$$
最後の合同式は $15 \equiv 1 \pmod{7}$ より $l \equiv 3 \pmod{7}$ です。$l = 7m + 3$ とすると $x = 15(7m + 3) + 8 = 105m + 53$ です。
最小の正の整数は $m = 0$ のとき $x = 53$ です。確認すると、$53 = 3 \times 17 + 2$, $53 = 5 \times 10 + 3$, $53 = 7 \times 7 + 4$ で、すべての条件を満たします。
例題3のような「異なる法での合同式の連立」が一意的に解けることを保証するのが中国剰余定理（Chinese Remainder Theorem）です。$n_1, n_2, \ldots, n_k$ が互いに素であるとき、任意の $a_1, a_2, \ldots, a_k$ に対して $x \equiv a_i \pmod{n_i}$（$i = 1, 2, \ldots, k$）を同時に満たす $x$ が $\mathrm{mod}\;n_1 n_2 \cdots n_k$ で一意に存在します。例題3では $3, 5, 7$ が互いに素なので、解は $\mathrm{mod}\;105$ で一意です。
Q1. $a \equiv b \pmod{n}$ の定義を、割り算の余りを使わずに述べてください。
Q2. $\mathrm{mod}\;12$ における $5$ の逆元を求めてください。
Q3. フェルマーの小定理を使って、$3^{50}$ を $7$ で割った余りを求めてください。
Q4. RSA暗号で、復号の計算 $c^d \pmod{n}$ が元の平文 $m$ に戻る理由を、オイラーの定理を用いて簡潔に説明してください。
次の合同式が成り立つかどうか判定し、理由を述べよ。
(1) $100 \equiv 2 \pmod{7}$
(2) $-15 \equiv 9 \pmod{8}$
(3) $2^{10} \equiv 1 \pmod{11}$
(1) $100 - 2 = 98 = 7 \times 14$ なので $7 \mid 98$。成り立ちます。
(2) $-15 - 9 = -24 = 8 \times (-3)$ なので $8 \mid (-24)$。成り立ちます。
(3) $2^{10} = 1024$, $1024 - 1 = 1023 = 11 \times 93$ なので $11 \mid 1023$。成り立ちます。（フェルマーの小定理 $2^{10} \equiv 1 \pmod{11}$ の確認でもあります。）
$\mathrm{mod}\;11$ における $4$ の逆元を求めよ。また、合同式 $4x \equiv 3 \pmod{11}$ を解け。
$4x \equiv 1 \pmod{11}$ を満たす $x$ を探します。$4 \times 3 = 12 \equiv 1 \pmod{11}$ なので、$4^{-1} \equiv 3 \pmod{11}$ です。
$4x \equiv 3 \pmod{11}$ の両辺に逆元 $3$ を掛けると、$x \equiv 3 \times 3 = 9 \pmod{11}$ です。
確認：$4 \times 9 = 36 = 3 \times 11 + 3$ なので $4 \times 9 \equiv 3 \pmod{11}$。正しいです。
$5^{200}$ を $13$ で割った余りを求めよ。
$\gcd(5, 13) = 1$ なので、フェルマーの小定理より $5^{12} \equiv 1 \pmod{13}$ です。
$200 = 12 \times 16 + 8$ なので、$5^{200} = (5^{12})^{16} \cdot 5^8 \equiv 1 \cdot 5^8 \pmod{13}$ です。
$5^2 = 25 \equiv 12 \equiv -1 \pmod{13}$ です。
$5^4 \equiv (-1)^2 = 1 \pmod{13}$ です。
$5^8 \equiv 1^2 = 1 \pmod{13}$ です。
よって $5^{200} \equiv 1 \pmod{13}$ で、余りは $1$ です。
$5$ で割ると $1$ 余り、$7$ で割ると $3$ 余る正の整数のうち、最小のものを求めよ。
$x \equiv 1 \pmod{5}$ より $x = 5k + 1$（$k$ は非負整数）。
第2条件に代入：$5k + 1 \equiv 3 \pmod{7}$ より $5k \equiv 2 \pmod{7}$。
$5$ の $\mathrm{mod}\;7$ における逆元を求めます。$5 \times 3 = 15 \equiv 1 \pmod{7}$ なので $5^{-1} \equiv 3 \pmod{7}$。
両辺に $3$ を掛けて $k \equiv 6 \pmod{7}$、すなわち $k = 7m + 6$ です。
$x = 5(7m + 6) + 1 = 35m + 31$ です。最小の正の整数は $m = 0$ のとき $x = 31$ です。
確認：$31 = 5 \times 6 + 1$, $31 = 7 \times 4 + 3$。正しいです。
任意の正の整数 $n$ に対して、$n^5 - n$ は $30$ で割り切れることを証明せよ。
$30 = 2 \times 3 \times 5$ なので、$n^5 - n$ が $2$, $3$, $5$ のそれぞれで割り切れることを示します。
$p = 5$ の場合： フェルマーの小定理より $n^5 \equiv n \pmod{5}$。よって $5 \mid (n^5 - n)$。
$p = 3$ の場合： フェルマーの小定理より $n^3 \equiv n \pmod{3}$。よって $n^5 = n^3 \cdot n^2 \equiv n \cdot n^2 = n^3 \equiv n \pmod{3}$。よって $3 \mid (n^5 - n)$。
$p = 2$ の場合： フェルマーの小定理より $n^2 \equiv n \pmod{2}$。よって $n^5 = (n^2)^2 \cdot n \equiv n^2 \cdot n = n^3 = n^2 \cdot n \equiv n \cdot n = n^2 \equiv n \pmod{2}$。よって $2 \mid (n^5 - n)$。
$2, 3, 5$ は互いに素なので $30 \mid (n^5 - n)$。$\square$