COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

倍数・約数

理論

倍数・約数

定義≪倍数・約数≫

 $a,$ $b$ を整数とする.
(1)
ある整数 $q$ に対して $a = bq$ が成り立つとき, $a$ は $b$ で割り切れる(be divided), $b$ は $a$ を割り切る(divide)といい, $a$ を $b$ の倍数(multiple), $b$ を $a$ の約数(divisor)と呼ぶ.
(2)
整数 $p$ が $1$ より大きく, $1,$ $p$ 以外の正の約数を持たないとき, $p$ を素数(prime number)と呼ぶ.
(3)
正整数 $n$ が $1,$ $n$ 以外の正の約数を持つとき, すなわち $1$ でも素数でもないとき, $n$ を合成数(composite number)と呼ぶ.
(4)
$a$ の倍数でも $b$ の倍数でもある整数を $a,$ $b$ の公倍数(common multiple)と呼ぶ. $a,$ $b$ の正の公倍数の最小値を $a,$ $b$ の最小公倍数(lowest common multiple)と呼ぶ.
(5)
$a$ の約数でも $b$ の約数でもある整数を $a,$ $b$ の公約数(common divisor)と呼ぶ. $a,$ $b$ の公約数の最大値を $a,$ $b$ の最大公約数(greatest common divisor)と呼ぶ.
(6)
$a,$ $b$ の最大公約数が $1$ であるとき, $a,$ $b$ は互いに素(coprime, relatively prime)であるという.

除法の定理

定理≪整数に関する除法の定理≫

 任意の整数 $a$ と正整数 $b$ に対して, \[ a = bq+r\ \cdots [1], \quad 0 \leqq r < b\ \cdots [2]\] を満たす整数 $q,$ $r$ が唯 $1$ 組存在する.

証明

 まず, $[1],$ $[2]$ を満たす $q,$ $r$ の存在を示す. すべての整数は
$bn \leqq x < b(n+1)$ ($n$: 整数)
の形の無限個の範囲に分けられる. よって, \[ bq \leqq a < b(q+1)\] なる整数 $q$ が存在する. このとき, \[ 0 \leqq a-bq < b\] となるから, 整数 $r$ を \[ r = a-bq\] により定めると, $q,$ $r$ は $[1],$ $[2]$ を満たす.
 次に, $q,$ $r$ の一意性を示す. 上記の $q,$ $r$ に加えて, \[ a = bq'+r'\ \cdots [1]', \quad 0 \leqq r' < b\ \cdots [2]'\] を満たす整数 $q',$ $r'$ の存在を仮定する. $[1],$ $[1]'$ の辺々を引くと, $b(q-q')+(r-r') = 0$ より, \[ r-r' = b(q'-q).\] よって, $r-r'$ は $b$ の倍数である. 一方, $[2],$ $[2]'$ より \[ -b < r-r' < b\] だから, $r-r' = 0$ すなわち $r = r'.$
これと $bq+r = bq'+r'$ より $bq = bq' = 0$ すなわち $b(q-q') = 0$ だから, $q-q' = 0$ すなわち $q = q'.$
以上より, $q,$ $r$ の一意性が示された.

存在の別証明:「全段仮定」の帰納法を利用

(I)
$a \geqq 0$ の場合. $a$ に関する数学的帰納法を使う.
(i)
$a = 0$ のとき. $q = r = 0$ に対して $[1],$ $[2]$ が成り立つ.
(ii)
$a > 0$ のとき. $a$ 未満の任意の非負整数に対して $q,$ $r$ の存在を仮定する.
  • $a < b$ のとき, $q = 0,$ $r = a$ に対して $[1],$ $[2]$ が成り立つ.
  • $a \geqq b$ のとき. $0 \leqq a-b < a$ だから, 帰納法の仮定より \[ a-b = bq_1+r_1, \quad 0 \leqq r_1 < b\] を満たす整数 $q_1,$ $r_1$ が存在する. $a = b(q_1+1)+r_1$ だから, $q = q_1+1,$ $r = r_1$ に対して $[1],$ $[2]$ が成り立つ.
(i), (ii) より, $a \geqq 0$ のとき $q,$ $r$ の存在が示された.
(II)
$a < 0$ の場合. $-a > 0$ と (I) より, \[ -a = bq_2+r_2, \quad 0 \leqq r_2 < b\] を満たす整数 $q_2,$ $r_2$ が存在する.
  • $r_2 = 0$ のとき, $q = -q_2,$ $r = 0$ に対して $[1],$ $[2]$ が成り立つ.
  • $r_2 > 0$ のとき, \[ a = b(-q_2-1)+(b-r_2), \quad 0 \leqq b-r_2 < b\] だから, $q = -q_2-1,$ $r = b-r_2$ に対して $[1],$ $[2]$ が成り立つ.
(I), (II) より, すべての場合に $q,$ $r$ の存在が示された.

定理≪連続する $m$ 個の整数の積≫

 連続する $m$ 個の整数の積は $m!$ の倍数である.

証明

 $(n+1)\cdots (n+m)$ が $m$ の倍数であることを示せば良い. $n$ を $m$ で割った余りが $r$ であるとき, $n+m-r$ は $m$ で割り切れる. $0 \leqq r < m$ から $-m < -r \leqq 0.$ よって, $n < n+m-r \leqq n+m.$ したがって, $n+m-r$ は $n+1,$ $\cdots,$ $n+m$ の中に含まれるから, $(n+1)\cdots (n+m)$ は $m$ の倍数である.

別証明: 二項係数の意味に着目

 連続する $m$ 個の整数の積 $(n-m+1)\cdots n = \dfrac{n!}{(n-m)!}$ が $m!$ の倍数であることは, $\dfrac{n!}{m!(n-m)!} = {}_n\mathrm C_m$ が整数であることに他ならない. ${}_n\mathrm C_m$ は $n$ 個から $m$ 個を選ぶ組合せの総数であるから, 整数である. 題意が示された.

ユークリッドの互除法

定理≪ユークリッドの互除法≫

 整数 $a$ を $0$ でない整数 $b$ で割った余りが $r$ であるとき, $a,$ $b$ の最大公約数は $b,$ $r$ の最大公約数に等しい.

証明

 除法の定理により
$a = bq+r$ ($q$: 整数)
と表せる. $a,$ $b$ の最大公約数を $g$ とおき, $b,$ $r$ の最大公約数を $h$ とおく.
(i)
$g$ は $b,$ $r = a-bq$ の公約数だから, $h$ の最大性により, $g \leqq h.$
(ii)
$h$ は $b,$ $a = bq+r$ の公約数だから, $g$ の最大性により, $g \geqq h.$
(i), (ii) より, $g = h.$

補足≪ラメの定理: ユークリッドの互除法の計算回数≫

 ユークリッドの互除法で正の整数 $a,\ b\ (a > b)$ の最大公約数を求めるのに必要な割り算の回数は, 最大でも $b$ を十進法で表したときの桁数の $5$ 倍であることが知られている(ラメの定理, 1844).

合同式

定義≪合同式≫

 $m$ を整数とする. 整数 $a,$ $b$ について, $a-b$ が $m$ の倍数のとき, $a,$ $b$ は $m$ を法として合同(congruent modulo $m$)であるといい, \[ a \equiv b \pmod m\] と表す. このような関係を合同関係と呼び, このような数式を合同式と呼ぶ.

注意

(1)
$m = 0$ を法とする合同関係は, 等号関係に他ならない.
(2)
$m = 1$ を法とする合同関係はすべて真である.
(3)
整数 $m$ を法とする合同関係と $-m$ を法とする合同関係は同値である.
以上より, 合同関係は $1$ より大きい整数 $m$ を法とする場合が本質的である. また, 任意の整数 $a$ に対して,
$a \equiv 0 \pmod m$ $\iff$ $a$ は $m$ の倍数である.

定理≪合同関係が同値関係であること≫

 $m$ を整数とする. 任意の整数 $a,$ $b,$ $c$ に対して, 次が成り立つ.
(1)
$a \equiv a \pmod m.$ 
(2)
$a \equiv b \pmod m$ $\Longrightarrow$ $b \equiv a \pmod m.$
(3)
$a \equiv b,$ $b \equiv c \pmod m$ $\Longrightarrow$ $a \equiv c \pmod m.$

証明

(1)
$a-a = 0 = m\cdot 0$ は $m$ の倍数である.
(2)
$a-b$ が $m$ の倍数ならば, $-(a-b) = b-a$ は $m$ の倍数である.
(3)
$a-b,$ $b-c$ が $m$ の倍数ならば, $(a-b)+(b-c) = a-c$ は $m$ の倍数である.

記法

 (3) のとき, $a \equiv b \equiv c \pmod m$ と書く. $1$ つの等式の中で $=$ と $\equiv \pmod m$ を併用しても良い.

定理≪合同式の性質≫

 $m$ を整数とする. 任意の整数 $a,$ $b,$ $a',$ $b'$ と正整数 $n$ に対して, 次が成り立つ.
(1)
$a \equiv a' \pmod m,$ $b \equiv b' \pmod m$ ならば, \begin{align*} a+b &\equiv a'+b' \pmod m \quad \cdots [1], \\ a-b &\equiv a'-b' \pmod m \quad \cdots [2], \\ ab &\equiv a'b' \pmod m \quad \cdots [3], \\ ca &\equiv ca' \pmod m \quad \cdots [4], \\ a^n &\equiv a'^n \pmod m \quad \cdots [5]. \end{align*}
(2)
$a,$ $m$ が互いに素ならば, 次のような $m$ と互いに素な整数 $x$ が存在する. \[ ax \equiv 1 \pmod m.\]

証明

(1)
$a-a',$ $b-b'$ が $m$ の倍数であるとすると, \begin{align*} (a-a')+(b-b') &= (a+b)-(a'+b'), \\ (a-a')-(b-b') &= (a-b)-(a'-b'), \\ (a-a')b+a'(b-b') &= ab-a'b' \end{align*} も $m$ の倍数である. $[4],$ $[5]$ は $[3]$ より従う.
(2)
$a,$ $m$ は互いに素だから, $m \neq 0.$ $ax \equiv 1 \pmod m \iff ax \equiv 1 \pmod{-m}$ だから, $m > 0$ の場合を示せば良い. $m = 1$ のとき, 任意の整数 $x$ に対して $ax \equiv 1 \pmod m$ が成り立つ. 以下, $m > 1$ の場合を考える. 整数 $b,$ $b'$ が \begin{align*} &ab \equiv ab' \pmod m \quad \cdots [1], \\ &0 \leqq b' \leqq b \leqq m-1 \quad \cdots [2] \end{align*} を満たすとき, $[1]$ より $ab-ab' = a(b-b')$ は $m$ の倍数となるが, $a$ が $m$ と互いに素であるという仮定から $b-b'$ が $m$ の倍数となり, $[2]$ より $b-b' = 0$ すなわち $b = b'$ となる. よって, 集合 $\{ ab|0 \leqq b \leqq m-1\}$ の要素は $m$ を法として互いに合同でない. したがって, この集合の要素を $m$ で割った余りは $0$ から $m-1$ までのすべての値をとる. 特に, $0$ 以上 $m-1$ 以下のある整数 $x$ に対して $ax$ を $m$ で割った余りが $1$ となり, $ax \equiv 1 \pmod m$ となる. $x,$ $m$ の最大公約数を $g$ とおき, $q = \dfrac{ax-1}{m}$ とおくと, \[ 1 = ax-mq = g\left( a\frac{x}{g}-\frac{m}{g}q\right)\] となるから, $g = 1.$ よって, $x,$ $m$ は互いに素である.

問題

倍数・約数

問題≪百五減算≫

 ある人の年齢は, $3$ で割ると $2$ 余り, $5$ で割ると $1$ 余り, $7$ で割ると $2$ 余る. この人の年齢を求めよ.

解答例

 求める年齢を $n$ とおく. 条件から, $n$ はある整数 $x,$ $y,$ $z$ を用いて \[ n = 3x+2 = 5y+1 = 7z+2\] と表される. $3x+2 = 5y+1$ から \[ 3(x+2) = 5(y+1)\] が成り立つので, $3$ と $5$ は互いに素であることから \[ x+2 = 5k, \quad y+1 = 3k\] なる整数 $k$ が存在する. また, $3x+2 = 7z+2$ から \[ 3x = 7z\] が成り立つので, $3$ と $7$ は互いに素であることから \[ x = 7l, \quad z = 3l\] なる整数 $l$ が存在する. よって, \[ x = 5k-2 = 7l\] から \[ 5(k+1) = 7(l+1)\] が成り立つので, $5$ と $7$ は互いに素であるから \[ k+1 = 7m, \quad l+1 = 5m\] なる整数 $m$ が存在する. したがって, \begin{align*} n &= 3x+2 = 3(5k-2)+2 = 15k-4 \\ &= 15(7m-1)-4 = 105m-19 \end{align*} が成り立つ. $m = 1$ として, 求める年齢は $n = 86$ である.

別解

 $5,$ $7$ で割り切れて $3$ で割ると $1$ 余る数として $70$ を,
$7,$ $3$ で割り切れて $5$ で割ると $1$ 余る数として $21$ を,
$3,$ $5$ で割り切れて $7$ で割ると $1$ 余る数として $15$ をとる. このとき, \[ 70\cdot 2+21\cdot 1+15\cdot 2 = 191\] は $3$ で割ると $2$ 余り, $5$ で割ると $1$ 余り, $7$ で割ると $2$ 余る.
この条件を満たす整数は, $3,$ $5,$ $7$ の最小公倍数である $105$ おきに現れるから, $191+105d$ ($d$: 整数)の形に表される.
現代で $191$ 以上という年齢は考えられないから, $d = -1$ として, 求める年齢は $86$ である.

解説・別解の方針

  • $3,$ $5,$ $7$ でそれぞれ割った余りから $105$ 以下の正整数を求める問題は, 百五減算と呼ばれ, 和算の問題として古くから知られていた. 本問は,『塵劫記』(じんこうき)という江戸初期の和算書の問題に年齢を決定するという味付けをしたものである.
  • $m_1 = 3,$ $m_2 = 5,$ $m_3 = 7$ とおく. 各番号 $k$ に対し, $0 \leqq r_k < m_k$ なる整数 $r_k$ について, $m_k$ で割ると $1$ 余る整数 $a_k = m_kq_k+1$ ($q_k$: 整数)をとると, $a_kr_k = (m_kq_k+1)r_k = m_kq_kr_k+r_k$ は $m_k$ で割ると $r_k$ 余る整数になることを使う(一般に「積の余りは余りの積の余り」). $a_k$ として整数 $m_i,$ $m_j$ ($\{ i,\ j,\ k\} = \{ 1,\ 2,\ 3\}$)の倍数を選んでおけば, $a_kr_k$ を $m_i,$ $m_j$ の倍数とすることができる. このとき, $a_ir_i+a_jr_j$ は $m_k$ で割り切れるから, $c = a_1r_1+a_2r_2+a_3r_3$ を $m_k$ で割った余りは $r_k.$
  • この方法で求まる数 $c$ が適当な大きさの値をとるとは限らない. 条件を満たす整数は $m = m_1m_2m_3$ おきに現れるから, $c$ に $m$ を足し引きして答えを求める.
  • 一般に, 互いに素な複数の整数 $m_1,$ $\cdots,$ $m_r$ で割った余りから $m_1\cdots m_r$ 以下の範囲で元の正整数を決定できるが, これは中国式剰余の定理と呼ばれる定理によって保証される.

問題≪指数関数の差の倍数性≫

 任意の正整数 $n$ に対して $f(n) = 5^n-3^n-2^n$ は $6$ の倍数であることを示せ.

解答例

\[ 5^n-3^n = (5-3)(5^{n-1}+5^{n-2}\cdot 3+\cdots +3^{n-1})\] は偶数だから, $f(n) = (5^n-3^n)-2^n$ は偶数である.
\[ 5^n-2^n = (5-2)(5^{n-1}+5^{n-2}\cdot 2+\cdots +2^{n-1})\] は $3$ の倍数だから, $f(n) = (5^n-2^n)-3^n$ は $3$ の倍数である.
$2,$ $3$ は互いに素だから, $f(n)$ は $2\cdot 3 = 6$ の倍数である.

問題≪指数関数の線形和の倍数性≫

 任意の正整数 $n$ に対して $3^{2n-1}+5^n$ は $4$ の倍数であることを示せ.

解答例

 $3 \equiv -1,$ $5 \equiv 1 \pmod 4$ だから, \[ 3^{2n-1}+5^n \equiv (-1)^{2n-1}+1^n = -1+1 = 0 \pmod 5.\] これは, $3^{2n-1}+5^n$ が $4$ の倍数であることを意味する.

問題≪最小公倍数・最大公約数からの復元≫

 $a,$ $b$ を正整数とし, $a \leqq b$ とする. $a,$ $b$ の最小公倍数を $l,$ 最大公約数を $g$ とおく. 次の各場合に, $a,$ $b$ の値を求めよ.
(a)
$l = 72,$ $g = 6.$ 
(b)
$a+b = 180,$ $g = 18.$ 
(c)
$ab = 2592,$ $l = 216.$ 

解答例

(a)
$g = 6$ より, 互いに素な正整数 $a',$ $b'$ を用いて \[ a = 6a', \quad b = 6b'\] と書ける. このとき, \[ 72 = l = 6a'b'\] より, \[ a'b' = 12.\] よって, $a \leqq b$ より $a' \leqq b'$ であること, $a',$ $b'$ は互いに素なことに注意すると,
$(a',\ b') = (1,\ 12)$ または $(a',\ b') = (3,\ 4).$
ゆえに,
$(a,\ b) = (6,\ 72)$ または $(a,\ b) = (18,\ 24).$
(b)
$g = 18$ より, 互いに素な正整数 $a',$ $b'$ を用いて \[ a = 18a', \quad b = 18b'\] と書ける. このとき, \[ 180 = a+b = 18a'+18b' = 18(a'+b')\] より, \[ a'+b' = 10.\] よって, $a \leqq b$ より $a' \leqq b'$ であること, $a',$ $b'$ は互いに素なことに注意すると,
$(a',\ b') = (1,\ 9)$ または $(a',\ b') = (3,\ 7).$
ゆえに,
$(a,\ b) = (18,\ 162)$ または $(a,\ b) = (54,\ 126).$
(c)
$ab = lg$ より, \[ g = \frac{ab}{l} = \frac{2592}{216} = 12.\] よって, 互いに素な正整数 $a',$ $b'$ を用いて \[ a = 12a', \quad b = 12b'\] と書ける. このとき, \[ 216 = l = 12a'b'\] より, \[ a'b' = 18.\] よって, $a \leqq b$ より $a' \leqq b'$ であること, $a',$ $b'$ は互いに素なことに注意すると,
$(a',\ b') = (1,\ 18)$ または $(a',\ b') = (2,\ 9).$
ゆえに,
$(a,\ b) = (12,\ 216)$ または $(a,\ b) = (24,\ 108).$

問題≪合同式で可逆な整数≫

 $m$ を正整数とし, 各整数 $n$ に対して $n$ を $m$ で割った余りを $\bar n$ で表すことにする. $a$ を $m$ と互いに素な整数とするとき, 次が成り立つことを示せ.
(1)
任意の整数 $b,$ $b'$ に対して $\overline{ab} = \overline{ab'} \Longrightarrow \bar b = \overline{b'}.$
(2)
ある整数 $x$ に対して $\overline{ax} = 1.$

解答例

(1)
整数 $n,$ $n'$ 対して $\bar n = \overline{n'}$ は $n-n'$ が $m$ の倍数であることと同値である.
$\overline{ab} = \overline{ab'}$ を仮定する. このとき, $ab-ab' = a(b-b')$ は $m$ の倍数だから, $a$ が $m$ と互いに素であるという仮定から $b-b'$ は $m$ の倍数である. これは $\bar b = \overline{b'}$ の成立を意味する.
(2)
(1) より, 任意の整数 $b,$ $b'$ に対して $\bar b \neq \overline{b'} \Longrightarrow \overline{ab} \neq \overline{ab'}.$
$\bar 1 = 1,$ $\cdots,$ $\overline{m-1} = m-1$ は互いに異なるから, $m-1$ 個の整数 $\overline{a\cdot 1},$ $\cdots,$ $\overline{a(m-1)}$ は互いに異なる. 定義より, これらは $1$ 以上 $m-1$ 以下だから, \[\{\overline{a\cdot 1},\ \cdots,\ \overline{a(m-1)}\} = \{ 1,\ \cdots,\ m-1\}.\] よって, $1$ 以上 $m-1$ 以下のある整数 $x$ に対して $\overline{ax} = 1$ となり, 題意が成り立つ.

問題≪最大公約数と $1$ 次不定方程式≫

 $a,$ $b,$ $g$ を正整数とする.
(1)
整数 $k$ に対して, $ak$ を $b$ で割った余りを $r(k)$ で表す. $a,$ $b$ が互いに素であるとき, $1$ 以上 $b-1$ 以下の整数 $i,$ $j$ に対して, 次が成り立つことを示せ. \[ r(i) = r(j) \Longrightarrow i = j.\]
(2)
$g$ が $a,$ $b$ の最大公約数であるならば, $ax+by = g$ の整数解が存在することを示せ.

解答例

(1)
前問を参照.
(2)
$g$ が $a,$ $b$ の最大公約数であるとする. 方程式 $ax+by = g$ の整数解の存在の証明は, 両辺を $g$ で割ることにより, $g = 1$ の場合, すなわち $a,$ $b$ が互いに素な場合に帰着する.
整数 $k$ に対して, $ak$ を $b$ で割った商を $q(k)$ で表すと, \[ ak-bq(k) = r(k).\] よって, $r(k) = 1$ なる整数 $k$ が存在することを示せば良い.
(1) の対偶を考えると, $1$ 以上 $b-1$ 以下の整数 $i,$ $j$ に対して \[ i \neq j \Longrightarrow r(i) \neq r(j)\] が成り立つから, \[\{ r(1),\ \cdots,\ r(b-1)\} = \{ 1,\ \cdots,\ b-1\}.\] よって, $r(k) = 1$ なる整数 $k$ が $1$ 以上 $b-1$ の整数の中から見つかる. 題意が示された.

問題≪最大公約数と $1$ 次不定方程式≫

 整数全体の集合を $Z$ で表す. $a,$ $b \in Z,$ $ab \neq 0$ として, \[ I = \{ ax+by|x,\ y \in Z\}\] とおく. さらに, 各整数 $m$ に対して $mZ = \{ mz|z \in Z\}$ と定める. このとき, 次が成り立つことを示せ.
(1)
$k_1,\ k_2 \in Z,\ n_1,\ n_2 \in I \Longrightarrow k_1n_1+k_2n_2 \in I.$ 
(2)
$I$ に属する最小の正整数を $d$ とおくとき, $I = dZ.$
(3)
$a,$ $b$ の最大公約数を $g$ とおくとき, $I = gZ.$

解答例

(1)
$n_j = ax_j+by_j\ (x_j,\ y_j \in Z,\ j \in \{ 1,\ 2\} )$ と表せるから, \begin{align*} &k_1n_1+k_2n_2 = k_1(ax_1+by_1)+k_2(ax_2+by_2) \\ &= a(k_1x_1+k_2x_2)+b(k_1y_1+k_2y_2) \in I. \end{align*}
(2)
(i)
$d \in I$ だから, (1) より各整数 $z$ に対して $dz \in I$ となる. すなわち, $dZ \subset I.$
(ii)
$n \in I$ とする. 除法の定理より $n = dq+r\ (q,\ r \in Z,\ 0 \leqq r < d)$ と表すと, (1) より \[ r = n-dq \in I\] となる. よって, $d$ の最小性より $r = 0$ となるから, $n = dq \in dZ.$ これは $I \subset dZ$ を意味する.
(i), (ii) より, $I = dZ.$
(3)
(i)
$a = ga',$ $b = gb',$ $d = ax+by$ $(a',$ $b',$ $x,$ $y \in Z)$ と表すと, 各整数 $z$ に対して \[ dz = (ga'x+gb'y)z = g(a'x+b'y)z \in gZ.\] よって, $dZ \subset gZ.$
(ii)
$a = a\cdot 1+b\cdot 0,$ $b = a\cdot 0+b\cdot 1$ は $I$ の要素だから, (2) より $a,$ $b$ は $d$ の倍数である. すなわち, $d$ は $a,$ $b$ の公約数だから, $g$ は $d$ の倍数である. よって, 各整数 $z$ に対して $gz$ は $d$ の倍数だから, $gz \in dZ.$ したがって, $gZ \subset dZ.$
(2) の結果と (i), (ii) より, $I = dZ = gZ.$

解説・方針

  • 最大公約数を特徴付ける次の定理の証明問題: 整数 $g$ は $a,$ $b$ の最大公約数である $\iff$ $ax+by = g$ の整数解が存在する. ちなみに, この定理を用いて素因数分解の一意性が証明され, その結果, 素因数分解を用いた最大公約数の計算などが可能になる. この周辺の整数論は, 本問のように, 集合論的に可換環論の言葉で整理されている. $Z$ のように結合法則・交換法則・分配法則を満たす和・差・積が定義された集合を可換環と呼び, (1) のような性質を満たす集合 $I$ を $Z$ のイデアルと呼ぶ.
  • $I \subset dZ$ を示すには, 除法の定理を用いる. つまり, $I$ の要素を $d$ で割った余りが $0$ であることを $d$ の最小性から示す.
  • $gZ \subset dZ$ を示すには, $d$ が $a,$ $b$ の公約数であることと $g$ の最大性を用いる.

問題≪フェルマーの小定理に関する倍数性≫

 任意の整数 $n$ に対して, $n^5-n$ は $30$ の倍数であることを示せ.

解答例

\begin{align*} n^5-n &= n(n^4-1) = n(n^2+1)(n^2-1) \\ &= (n-1)n(n+1)(n^2+1) \quad \cdots [1]. \end{align*} であり, $(n-1)n(n+1)$ は $3! = 6$ の倍数だから, $n^5-n$ は $6$ の倍数である. $30 = 6\cdot 5$ であり, $6$ と $5$ は互いに素だから, $n^5-n$ が $5$ の倍数であることを示せば良い.
$n$ を $5$ で割った余りで場合分けして, $[1]$ のある因数が $5$ の倍数であることを示す.
(i)
$n = 5q$ ($q$: 整数)のとき, $n$ は $5$ の倍数である.
(ii)
$n = 5q\pm 1$ ($q$: 整数)のとき, \[ n\mp 1 = (5q\pm 1)\mp 1 = 5q\] は $5$ の倍数である.
(iii)
$n = 5q\pm 2$ ($q$: 整数)のとき, \[ n^2+1 = (5q\pm 2)^2+1 = 5(5q^2\pm 4q+1)\] は $5$ の倍数である.
以上より, $n^5-n$ は $30$ の倍数である.

別解

\begin{align*} &n^5-n = n(n^4-1) = n(n^2-1)(n^2+1) \\ &= (n-1)n(n+1)(n^2+1) \\ &= (n-1)n(n+1)(n^2-4+5) \\ &= (n-1)n(n+1)(n^2-4)+5(n-1)n(n+1) \\ &= (n-2)(n-1)n(n+1)(n+2)+5(n-1)n(n+1). \end{align*} ここで, $(n-2)(n-1)n(n+1)(n+2)$ は $5!/4 = 30$ の倍数である. また, $(n-1)n(n+1)$ は $3! = 6$ の倍数であるから, $5(n-1)n(n+1)$ は $30$ の倍数である. よって, これらの和として表される $n^5-n$ は $30$ の倍数である.

解説・方針

  • 次のフェルマーの小定理(Fermat's little theorem)を背景にした頻出問題: 任意の素数 $p,$ 整数 $n$ に対して $n^p-n$ は $p$ の倍数である. その証明問題は次の問題またはこちらを参照.
  • $n^5-n$ を因数分解し, 連続する $r$ 個の整数の積は $r!$ の倍数であることを使う.
  • $n$ を $5$ で割った余りで場合分けして, $n^5-n$ が $5$ の倍数であることを示す.
  • なお, 連続する $5$ 個の整数の積が $5$ の倍数であることを使えるように, 無理やり式変形する別解もある. つまり, $n^5-n = (n-1)n(n+1)(n^2+1)$ となるので, $(n-2)(n-1)n(n+1)(n+2)$ が $5$ の倍数であることを使えるように, $n^2+1$ の部分を $(n-2)(n+2)$ を用いて表す.

問題≪合同式の性質とフェルマーの小定理≫

 $m,$ $r,$ $r',$ $s,$ $s'$ を整数とし, $a,$ $a',$ $c$ を素数 $p$ と互いに素な整数とする. 次を示せ.
(1)
$r \equiv r',$ $s \equiv s' \pmod m$ $\Longrightarrow$ $rs \equiv r's' \pmod m.$
(2)
$ca \equiv ca' \pmod p$ $\Longrightarrow$ $a \equiv a' \pmod p.$
(3)
$1$ 以上 $p-1$ 以下の整数全体から成る集合を $G$ とおく. $k \in G$ なる各整数 $k$ に対して $ka$ を $p$ で割った余りを $\overline{ka}$ とおくと, $\{\overline{ka}|k \in G\} = G.$
(4)
$a^{p-1} \equiv 1 \pmod p.$

解答例

(1)
$r = r'+md,$ $s' = s'+me$ ($d,$ $e$: 整数)とおくと, \[ rs = r's'+m(ds'+r'e+mde) \equiv r's' \pmod m.\]
(2)
合同式の定義より,
$ca \equiv ca' \pmod p$ $\iff$ $ca-ca'$ は $p$ の倍数
$\iff$ $c(a-a')$ は $p$ の倍数
$\iff$ $a-a'$ は $p$ の倍数 ($\because$ $c$ は $p$ と互いに素)
$\iff$ $a \equiv a' \pmod p.$
(3)
$i \in G,$ $j \in G,$ $i \neq j$ なる整数 $i,$ $j$ に対して, $a$ は $p$ と互いに素であるという仮定と $i \not\equiv j \pmod p$ から, (2) の対偶より, $ia \not\equiv ja \pmod p$ すなわち $\overline{ia} \neq \overline{ja}$ が成り立つ.
これは $\{\overline{ka}|k \in G\} = G$ が成り立つことを意味する.
(4)
$k \in G$ なるすべての整数 $k$ について $ka \equiv \overline{ka} \pmod p$ の辺々を掛け合わせると, (1), (3) より, \[ (p-1)!a^{p-1} \equiv (p-1)! \pmod p.\] $(p-1)!$ は $p$ と互いに素だから, (2) より, \[ a^{p-1} \equiv 1 \pmod p.\]

解説・方針

  • (4) のフェルマーの小定理(Fermat's little theorem)を示す誘導問題.
    前問のように, フェルマーの小定理を背景とする入試問題も多数出題されている.
  • (1) の「積の余り$=$余りの積」という事実は, 合同式を使うことで簡潔に述べられる.
  • $\overline{ka}$ $(k \in G)$がどの値をとるかは複雑であるが, $k$ を動かすと $1$ から $p-1$ までのすべての値をとるという (3) が証明のポイントである.

補足≪フェルマーの素数判定法≫

 $1$ より大きい整数 $n$ について,「$n$ が素数 $\Longrightarrow$ $0 \leqq a < n$ なる各整数 $a$ に対して $a^n \equiv a \pmod n$」の対偶をとると, 「$0 \leqq a < n$ なるある整数 $a$ に対して $a^n \not\equiv a \pmod n$ $\Longrightarrow$ $n$ は合成数」となる. これを利用して, 素数の候補を見つける方法は「フェルマーテスト」と呼ばれる.

補足≪ウィルソンの定理≫

 素数を法とする合同式についても剰余の定理(等式を合同式に置き換えた定理)が知られており, それを用いるとフェルマーの小定理からウィルソンの定理(Wilson's theorem)
$p$ が素数 $\Longrightarrow$ $(p-1)! \equiv -1 \pmod p \quad \cdots [\ast ]$
を導くことができる. 実際, 多項式 $f(x) = x^{p-1}-1$ について, $k \in G$ なる各整数 $k$ に対し $f(k) \equiv 0 \pmod p$ が成り立つから, 剰余の定理により, \[ f(x) \equiv (x-1)\cdots \big( x-(p-1)\big) \pmod p.\] これに $x = 0$ を代入すると, \[ -1 \equiv (-1)^{p-1}(p-1)! \pmod p.\] $p \geqq 3$ のとき, $p$ は奇数だから, $(-1)^{p-1} = 1$ より $[\ast ]$ が成り立つ.
$p = 2$ のときは, $(2-1)! = 1 \equiv -1 \pmod 2$ より, $[\ast ]$ が成り立つ.
ちなみに, ウィルソンの定理の逆が成り立つことも知られている.

問題≪RSA 暗号の原理≫

 $p,$ $q$ を相異なる素数とし, 整数 $d,$ $e$ が \[ de \equiv 1 \pmod{(p-1)(q-1)}\] を満たすとする. 整数 $a,$ $b$ に対して $a^d \equiv b \pmod{pq}$ ならば $b^e \equiv a \pmod{pq}$ が成り立り立つことを, 前問の結果を用いて示せ.

解答例

 仮定から, ある整数 $m$ に対して \[ de = (p-1)(q-1)m+1\] と表せる. \begin{align*} b^e &\equiv (a^d)^e = a^{de} \\ &= a^{(p-1)(q-1)m+1} = (a^{p-1})^{(q-1)m}a \\ &\equiv 1^{(q-1)m}a = a \pmod p. \end{align*} 同様に, $b^e \equiv a \pmod q.$ よって, $b^e-a$ は $p,$ $q$ の倍数であるが, $p,$ $q$ は相異なる素数だから $b^e-a$ は $pq$ の倍数である. すなわち, $b^e \equiv a \pmod{pq}.$

解説≪RSA 暗号≫

  • 本問は, RSA 暗号の復号の原理を背景としている. RSA 暗号は, 電子メールやインターネット通信, カード情報の処理など, 情報化社会のさまざまな場面で使われている.
  • 上記の整数 $n,$ $d,$ $e$ を用いて, RSA 暗号と呼ばれる暗号が, 次の方法で実現できる. 通信は, 文字の代わりに整数で行われる.
    • 公開鍵の公開: $n,$ $d$ の値を送信者と受信者の間で共有する.
    • 暗号文の送信: 送信者は, 整数 $a$ $(0 \leqq a < n)$の値を伝えたいとき, $a^d$ を $n$ で割った余り $b$ の値を受信者に送る.
    • 復号: 受信者は, 秘密にしておいた $e$ の値を用いて, $b^e$ を $n$ で割った余りを計算して, 送信者が元々伝えたかった整数 $a$ の値を求める(なぜこの方法で元の値が求まるのかを上で示した).
  • RSA 暗号は, 巨大な整数の素因数分解の難しさにより通信の安全性が保証されているため, $p,$ $q$ を数百桁の素数として実装されている.
  • $p,$ $q$ が十分に値の大きい妥当な素数であれば, $n,$ $d$ の値を誰に知られても現在のテクノロジーでは暗号が破られることはない. この暗号方式のメリットは, 受信者が $n,$ $d$ の値を公開するだけで複数の送信者に安全に暗号化の方法を知らせられるという点である. このような暗号方式を公開鍵暗号方式と呼ぶ.

問題≪ピタゴラス素数≫

 奇数である素数 $p$ が $p = a^2+b^2$ ($a,$ $b$: 整数)の形に表されるならば, $p$ を $4$ で割った余りは $1$ であることを示せ.

解答例

(i)
$n = 2q$ ($q$: 整数)のとき, \[ n^2 = (2q)^2 = 4q^2\] を $4$ で割った余りは $0.$
(ii)
$n = 2q+1$ ($q$: 整数)のとき, \[ n^2 = (2q+1)^2 = 4(q^2+q)+1\] を $4$ で割った余りは $1.$
(i), (ii) より, すべての整数 $n$ に対して, $n^2$ を $4$ で割った余りは $0$ または $1$ である. よって, すべての整数 $a,$ $b$ に対して, $a^2+b^2$ を $4$ で割った余りは $0,$ $1,$ $2$ のいずれかであり, $3$ となることはない. ゆえに, 奇数である素数 $p$ が $p = a^2+b^2$ ($a,$ $b$: 整数)の形に表されるならば, $p$ を $4$ で割った余りは $1$ である.

解説

 実は, この逆が成り立つことが「フェルマーの $2$ 平方和定理」として知られている. $4$ で割った余りが $1$ である素数 $p$ は, $p = a^2+b^2$ と表され, \[ p^2 = a^4+2a^2b^2+b^4 = (a^2-b^2)^2+(2ab)^2\] からピタゴラスの三角形(各辺の長さが整数である直角三角形)の斜辺の長さになるので, 「ピタゴラス素数」と呼ばれる. 「フェルマーの $2$ 平方和定理」と $2 = 1^2+1^2$ とブラーマグプタの恒等式 \[ (a^2+b^2)(c^2+d^2) = (ac+bd)^2+(ad-bc)^2\] から, 整数 $n$ が $2$ つの平方数の和として表されるためには, $n$ の素因数分解において $4$ で割った余りが $3$ であるような素因数の指数が偶数であることが必要十分であることが分かる. $2017$ は $4$ で割った余りが $1$ である素数であるので, $2017 = a^2+b^2$ を満たす整数 $a,$ $b$ を求めてみよう. \[ 44^2 = 1936 < 2017 < 2025 = 45^2 \quad \cdots [\ast ]\] であるから, $1 \leqq a \leqq b \leqq 44$ の範囲に絞り込める. 十進法で平方数の $1$ の位は $1,$ $4,$ $5,$ $6,$ $9$ のいずれかであるので, $2017$ との差を考えると $a^2$ の $1$ の位は $1$ または $6$ である. よって, $a$ の位は $1,$ $4,$ $6,$ $9$ の場合に絞り込める. $2017-1^2 = 2016,$ $2017-4^2 = 2001,$ $2017-6^2 = 1981$ は平方数でないが, $2017-9^2 = 1936 = 44^2$ は平方数であることが $[\ast ]$ から分かる. よって, \begin{align*} 2017 &= 9^2+44^2, \\ 2017^2 &= (44^2-9^2)^2-(2\cdot 44\cdot 9)^2 = 1855^2+792^2 \end{align*} と表される. 受験生は, $2017$ が素数であることを覚えておきたい.

問題≪ピタゴラス数の偶奇性≫

(1)
すべての整数 $n$ に対して, $n^2$ を $4$ で割った余りは $0$ または $1$ であることを示せ.
(2)
$a,$ $b,$ $c$ を整数とする. $a^2+b^2 = c^2$ ならば, $a,$ $b$ の少なくとも一方は偶数であることを示せ.

解答例

(1)
前問の解答例を参照.
(2)
対偶を示すため, $a,$ $b$ を奇数として, $a^2+b^2 \neq c^2$ を示す.
$a^2,$ $b^2$ を $4$ で割った余りは $1$ だから, $a^2+b^2$ を $4$ で割った余りは, $2.$
任意の整数 $c$ に対して, $c^2$ を $4$ で割った余りは $0$ または $1$ だから, $a^2+b^2 \neq c^2.$
ゆえに, 対偶は真だから, 元の命題も真である.

問題≪ピタゴラス数の性質≫

 整数 $a,$ $b,$ $c$ が $a^2+b^2 = c^2$ を満たすとき, 次が成り立つことを示せ.
(a)
$a,$ $b$ のうち少なくとも一方は $3$ の倍数である.
(b)
$a,$ $b$ のうち少なくとも一方は $4$ の倍数である.
(c)
$a,$ $b,$ $c$ のうち少なくとも $1$ つは $5$ の倍数である.

解答例

(a)
$a,$ $b$ が $3$ の倍数でないとして, $a^2+b^2$ が平方数でないことを示せば良い. 任意の整数は $n = 3d+e$ ($d,$ $e$: 整数, $-1 \leqq e \leqq 1$)と表せる. 平方数 \[ n^2 = (3d+e)^2 = 3(3d^2+2de)+e^2\] を $3$ で割った余りは $e^2 = 0,$ $1$ であることに注意すると, $a,$ $b$ の取り方より $a^2+b^2$ を $3$ で割った余りは $1+1 = 2$ となるから, $a^2+b^2$ は平方数でない.
(b)
$a,$ $b$ が $4$ の倍数でないとして, $a^2+b^2$ が平方数でないことを示せば良い.
(i)
$a,$ $b$ が奇数のとき. 任意の奇数は $m = 2d+1$ ($d$: 整数)と表せ, \[ m^2 = (2d+1)^2 = 4d(d+1)+1 \quad \cdots [1]\] を $4$ で割った余りは $1$ である. $a,$ $b$ の取り方より $a^2+b^2$ を $4$ で割った余りは $1+1 = 2$ である. $a^2+b^2$ は, $2$ で割り切れる回数が奇数だから, 平方数でない.
(ii)
$a,$ $b$ の一方のみが奇数のとき. $a$ を奇数として一般性を失わない. 奇数 $m = 2d+1$ について $[1]$ より $m^2$ を $8$ で割った余りは $1$ である. また, $4$ の倍数でない任意の偶数は $n = 4e+2$ ($e$: 整数)と表せ, \[ n^2 = (4e+2)^2 = 8\cdot 2e(e+1)+4 \quad \cdots [2]\] を $8$ で割った余りは $4$ である. $a,$ $b$ の取り方より $a^2+b^2$ を $8$ で割った余りは $1+4 = 5$ だから, $a^2+b^2$ は平方数でない.
(iii)
$a,$ $b$ が $4$ の倍数でない偶数のとき. このような偶数 $n = 4e+2$ について $[2]$ より $n^2$ を $16$ で割った余りは $4$ である. $a,$ $b$ の取り方より $a^2+b^2$ を $16$ で割った余りは $4+4 = 8$ である. $a^2+b^2$ は, $2$ で割り切れる回数が奇数だから, 平方数でない.
(c)
$a,$ $b$ が $5$ の倍数でないとして, $a^2+b^2$ が平方数ならば $a^2+b^2$ は $5$ の倍数であることを示せば良い. 任意の整数は $n = 5d+e$ ($d,$ $e$: 整数, $-2 \leqq e \leqq 2$)と表せる. 平方数 \[ n^2 = (5d+e)^2 = 5(5d^2+2de)+e^2\] を $5$ で割った余りは $e^2 = 0,$ $1,$ $4$ であることに注意すると, $a,$ $b$ の取り方より $a^2+b^2$ を $5$ で割った余りは \[ 1+1 = 2, \quad 1+4 = 5, \quad 4+4 = 8\] を $5$ で割った余り $2,$ $0,$ $3$ のいずれかとなるから, $a^2+b^2$ が平方数ならば $a^2+b^2$ は $5$ の倍数である(第 $2$ の場合のみ起こる).

別解: 合同式を用いる

(a)
$a,$ $b$ がともに $3$ の倍数でないとして, $a^2+b^2$ は平方数でないことを示せば良い. \[ n^2 \equiv \begin{cases} 0^2 = 0 \pmod 3 & (n \equiv 0 \pmod 3), \\ (\pm 1)^2 = 1 \pmod 3 & (n \equiv \pm 1 \pmod 3) \end{cases}\] に注意すると, $a \equiv \pm 1 \pmod 3,$ $b \equiv \pm 1 \pmod 3$ より \[ a^2+b^2 \equiv 1+1 = 2\pmod 3\] だから, $a^2+b^2$ は平方数でない.
(b)
$a,$ $b$ がともに $4$ の倍数でないとして, $a^2+b^2$ が平方数でないことを示せば良い.
(i)
$a \equiv \pm 1,$ $b \equiv \pm 1 \pmod 4$ のとき. \[ a^2+b^2 \equiv 1+1 = 2 \pmod 4\] より $a^2+b^2$ は偶数であるが $2$ で割り切れる回数が奇数だから平方数でない.
(ii)
$a,$ $b$ の一方のみが奇数のとき. $a \equiv \pm 1,$ $b \equiv 2 \pmod 4$ として一般性を失わない.
$a = 4d\pm 1,$ $b = 4e+2$ ($d,$ $e$: 整数)
と表すと \begin{align*} a^2 &= 4d(d\pm 1)+1 \equiv 1 \pmod 8 \quad \cdots [\ast ], \\ b^2 &= 16e^2\pm 8e+4 \equiv 4 \pmod 8 \end{align*} となる. よって, \[ a^2+b^2 \equiv 1+4 = 5 \pmod 8\] より $a^2+b^2$ は奇数であるが $8$ で割った余りが $1$ でないので $[\ast ]$ より平方数でない.
(iii)
$a \equiv 2,$ $b \equiv 2 \pmod 4$ のとき. \[ a^2+b^2 \equiv 4+4 = 8 \pmod{16}\] より, $a^2+b^2$ は偶数であるが $2$ で割り切れる回数が奇数だから平方数でない.
(c)
$a,$ $b$ がともに $5$ の倍数でないとして, $c$ が $5$ の倍数であることを示せば良い. \[ n^2 \equiv \begin{cases} 0^2 = 0 \pmod 5 & (n \equiv 0 \pmod 5), \\ (\pm 1)^2 = 1 \pmod 5 & (n \equiv \pm 1 \pmod 5), \\ (\pm 2)^2 = 4 \pmod 5 & (n \equiv \pm 2 \pmod 5) \end{cases}\] に注意する. 仮定より $a^2,$ $b^2$ を $5$ で割った余りは $1$ または $4$ だから, $a^2+b^2$ を $5$ で割った余りは $0,$ $2,$ $3$ のいずれかである. 一方, $a^2+b^2 = c^2$ と上の注意より, $c^2$ を $5$ で割った余りは $0$ でなければならない. これは $c$ が $5$ の倍数であることを意味する.

補足

 (a), (b) より各辺の長さが整数である直角三角形の面積は $6$ の倍数であることが分かる.

問題≪原始ピタゴラス数≫

 互いに素な正整数 $a,$ $b,$ $c$ が $a^2+b^2 = c^2$ を満たすとき, 次が成り立つことを示せ.
(1)
$a,$ $b$ の偶奇は異なり, $c$ は奇数である.
(2)
$a$ が奇数のとき, $\dfrac{c+a}{2},$ $\dfrac{c-a}{2}$ はいずれも互いに素な平方数である.
(3)
$a$ が奇数のとき, $a,$ $b,$ $c$ は互いに素なある整数 $m,$ $n$ を用いて $a = m^2-n^2,$ $b = 2mn,$ $c = m^2+n^2$ と表される.

解答例

(1)
(i)
仮に $a,$ $b$ がともに偶数であるとすると, $a^2+b^2 = c^2$ は偶数となり, $c$ は偶数となる. これは $a,$ $b,$ $c$ が互いに素であることに反する.
(ii)
仮に $a,$ $b$ がともに奇数であるとすると, $(2x+1)^2 = 4(x^2+x)+1$ より $a^2,$ $b^2$ を $4$ で割った余りは $1$ となり, $a^2+b^2$ を $4$ で割った余りは $2$ となって, $a^2+b^2$ が $2$ で割り切れる回数は奇数となり, $a^2+b^2$ は非平方数となる. これは $a^2+b^2 = c^2$ に反する.
(i), (ii) より, $a,$ $b$ の偶奇は異なり, したがって $c$ は奇数である.
(2)
$c^2-a^2 = b^2$ より, \[\frac{c+a}{2}\cdot\frac{c-a}{2} = \left(\frac{b}{2}\right) ^2.\] $\dfrac{c+a}{2},$ $\dfrac{c-a}{2}$ の共通因数は, これらの和, 差である $a,$ $c$ の共通因数となるから, $\pm 1$ に限る. つまり, $\dfrac{c+a}{2},$ $\dfrac{c-a}{2}$ は互いに素である. 以上より, $\dfrac{c+a}{2},$ $\dfrac{c-a}{2}$ はともに平方数でなければならない. そうでなければ $\dfrac{c+a}{2},$ $\dfrac{c-a}{2}$ の共通の素因数が存在してしまうからである.
(3)
(2) より, \[\dfrac{c+a}{2} = m^2, \quad \dfrac{c-a}{2} = n^2\] を満たす互いに素な正整数 $m,$ $n$ が存在する. このとき, \[ a = m^2-n^2, \quad c = m^2+n^2.\] $\dfrac{b^2}{4} = m^2n^2$ より, $b > 0$ に注意すると, \[ b = 2mn.\]

別解: 合同式を用いる

(1)
(ii)
仮に $a,$ $b$ がともに奇数であるとすると, \[ a^2 \equiv b^2 \equiv 1 \pmod 4\] より \[ a^2+b^2 \equiv 2 \pmod 4\] となって, $a^2+b^2$ が $2$ で割り切れる回数は奇数となり, $a^2+b^2$ は非平方数となる. これは $a^2+b^2 = c^2$ に反する.

ユークリッドの互除法

問題≪ユークリッドの互除法≫

(1)
整数 $a$ を $0$ でない整数 $b$ で割った余りが $r$ であるとき, $a,$ $b$ の最大公約数は $b,$ $r$ の最大公約数に等しいことを示せ.
(2)
$4123,$ $1729$ の最大公約数を求めよ.

解答例

(1)
こちらを参照.
(2)
\begin{align*} 4123 &= 2\cdot 1729+665 \\ 1729 &= 2\cdot 665+399 \\ 399 &= 1\cdot 266+133, \\ 266 &= 2\cdot 133. \end{align*} ゆえに, (1) より, $a,$ $b$ の最大公約数を $\mathrm{gcd}(a,\ b)$ で表すことにすると, \begin{align*} &\mathrm{gcd}(4123,\ 1729) = \mathrm{gcd}(1729,\ 665) \\ &= \mathrm{gcd}(665,\ 399) = \mathrm{gcd}(399,\ 266) \\ &= \mathrm{gcd}(266,\ 133) = 133. \end{align*}

解説

 $4123 = 7\cdot 19\cdot 31,$ $1729 = 7\cdot 13\cdot 19$ のように, 大きい数や素因数分解が難しい数の最大公約数を求める際に, ユークリッドの互除法は有用である.

問題≪多項式で表された整数の最大公約数≫

 $5n+1,$ $4n+2$ の最大公約数が $3$ であるような $1$ 以上 $100$ 以下の整数 $n$ の総数を求めよ.

解答例

 $n$ を正整数とする.
(i)
$n = 1$ のとき. $5n+1 = 6,$ $4n+2 = 6$ の最大公約数は $6 \neq 3.$
(ii)
$n \geqq 2$ のとき. $4n+2,$ $n-1$ も正整数であり, \begin{align*} 5n+1 &= (4n+2)\cdot 1+(n-1), \\ 4n+2 &= (n-1)\cdot 4+6 \end{align*} だから, ユークリッドの互除法より $5n+1,$ $4n+2$ の最大公約数は $4n+2,$ $n-1$ の最大公約数に等しく, $n-1,$ $6$ の最大公約数に等しい.
よって, $6 = 2\cdot 3$ に注意すると, $5n+1,$ $4n+2$ の最大公約数が $3$ であるためには, $n-1$ が偶数でない $3$ の倍数であることが必要十分である.
$n$ が $2$ 以上 $100$ 以下の整数のとき, $1 \leqq n-1 \leqq 99$ で, この範囲に $3$ の倍数は $33$ 個, $6$ の倍数は $16$ 個あるから, 偶数でない $3$ の倍数は $17$ 個ある.
(i), (ii) より, 求める整数の個数は $17.$

素数・素因数分解

問題≪因数分解を用いた素因数分解≫

 次の整数を素因数分解せよ.
(a)
$8099.$ 
(b)
$26999.$ 
(c)
$8027.$ 

解答例

(a)
\begin{align*} 8099 &= 8100-1 = 90^2-1^2 \\ &= (90-1)(90+1) = 89\cdot 91 \\ &= 7\cdot 13\cdot 89. \end{align*} $7,$ $13$ は素数である. $\sqrt{89} < \sqrt{100} = 10$ であり, $89$ は $10-1 = 9$ 以下の素数 $2,$ $3,$ $5,$ $7$ で割り切れないから, $89$ も素数である. よって, 求める素因数分解は, $8099 = 7\cdot 13\cdot 89.$
(b)
\begin{align*} 26999 &= 27000-1 = 30^3-1^3 \\ &= (30-1)(30^2+30\cdot 1+1^2) = 29\cdot 931 \\ &= 7^2\cdot 19\cdot 29. \end{align*} $7,$ $19,$ $29$ は素数だから, これが求める素因数分解である.
(c)
\begin{align*} 8027 &= 8000+27 = 20^3+3^3 \\ &= (20+3)(20^2-20\cdot 3+3^2) \\ &= 23\cdot 349. \end{align*} $\sqrt{349} < \sqrt{361} = 19$ であり, $349$ は $19-1 = 18$ 以下の素数 $2,$ $3,$ $5,$ $7,$ $11,$ $13,$ $17$ で割り切れないから, $349$ も素数である. よって, 求める素因数分解は, $8027 = 23\cdot 349.$

問題≪$2$ 次式で表される素数≫

 $f(n) = 3n^2-10n+8$ が素数となるような整数 $n$ とその素数の値を求めよ.

解答例

\begin{align*} f(n) &= 3n^2-10n+8 \\ &= (n-2)(3n-4). \\ \therefore |f(n)| &= |n-2||3n-4|. \end{align*} $f(n)$ が素数のとき, $|f(n)|$ も素数だから, $|n-2| = 1$ または $|3n-4| = 1.$
よって, $n-2 = \pm 1$ または $3n-4 = \pm 1.$
(i)
$n-2 = 1$ のとき, $n = 3$ より, $f(n) = 5.$
(ii)
$n-2 = -1$ のとき, $n = 1$ より, $f(n) = 1.$
(iii)
$3n-4 = 1$ すなわち $3n = 5$ を満たす整数 $n$ は存在しない.
(iv)
$3n-4 = -1$ すなわち $3n = 3$ のとき, $n = 1$ より, $f(n) = 1.$
ゆえに, $f(n)$ が素数となるのは, $n = 3$ のときに限り, その素数の値は $5.$

問題≪素数の逆数の和≫

 相異なる任意の素数 $p,$ $q$ に対して, \[\frac{1}{p}+\frac{1}{q} = \frac{1}{n} \quad \cdots [\ast ]\] を満たす整数 $n$ は存在しないことを示せ.

解答例

 $[\ast ]$ を満たす整数 $n$ の存在を仮定して矛盾を導く. \begin{align*} [\ast ] &\iff \frac{p+q}{pq} = \frac{1}{n} \\ &\iff (p+q)n = pq \quad \cdots [1]. \end{align*} $p$ は $p$ で割り切れるが $q$ は $p$ で割り切れないから, $p+q$ は $p$ で割り切れない.
同様に, $p+q$ は $q$ で割り切れない.
よって, $p+q$ は $pq$ で割り切れない.
これと $[1]$ より, $n$ は $pq$ で割り切れ, ある整数 $r$ を用いて \[ n = pqr\] と書ける. $[1]$ の両辺を $pq$ で割ると, \[ (p+q)r = 1 \quad \cdots [2].\] 一方, $p+q > 0,$ $pq > 0$ より $n > 0$ だから, $r > 0.$
また, $p+q \geqq 2+3 = 5.$ \[\therefore (p+q)r \geqq 5.\] これは $[2]$ に反する.
ゆえに, $[\ast ]$ を満たす整数 $n$ は存在しない.

問題≪メルセンヌ素数≫

 $n$ を正の整数とする. $2^n-1$ が素数ならば, $n$ は素数であることを示せ.

解答例

 対偶を示すため, $n$ を $1$ または合成数とし, $2^n-1$ は $1$ または合成数であることを示す.
(i)
$n = 1$ のとき. $2^n-1 = 2^1-1 = 1.$
(ii)
$n$ が合成数のとき. ある $1$ より大きい整数 $\ell,$ $m$ に対して, \[ n = \ell m\] となるから, \begin{align*} 2^n-1 &= 2^{\ell m}-1 = (2^\ell )^m-1 \\ &= (2^\ell -1)((2^\ell )^{m-1}+\cdots +1) \end{align*} となる. $\ell > 1,$ $m > 1$ より, \begin{align*} &2^\ell -1 > 2^1-1 = 1, \\ &(2^\ell )^{m-1}+\cdots +1 > 1. \end{align*}
よって, $2^n-1$ は合成数である.
(i), (ii) より対偶は真だから, 元の命題も真である.

問題≪フェルマー素数≫

 $m$ を正の整数とする. $2^m+1$ が素数ならば, ある非負整数 $n$ に対して $m = 2^n$ となることを示せ.

解答例

 対偶を示すため, $m$ が奇素数 $p$ で割り切れるとする. $q = \dfrac{m}{p}$ とおく. このとき, \begin{align*} 2^m+1 &= (2^q)^p+1 \\ &= (2^q+1)((2^q)^{p-1}-(2^q)^{p-2}+\cdots +1) \end{align*} は, $1$ でも $2^m+1$ でもない正の約数 $2^q+1$ を持つので, 合成数である. よって, 対偶は真だから, 元の命題も真である.

問題≪公差 $2$ の $3$ つ子素数≫

 $n$ を正整数とする.
(1)
次の命題の対偶を述べよ.
''$n,$ $n+2,$ $n+4$ はすべて素数 $\Longrightarrow$ $n = 3$'' $\cdots [\ast ].$
(2)
$n$ を $3$ で割った余りに着目して, $[\ast ]$ は真であることを示せ.

解答例

(1)
$[\ast ]$ の対偶は,
''$n \neq 3$ $\Longrightarrow$ $n,$ $n+2,$ $n+4$ の少なくとも    
$1$ つは素数でない'' $\cdots [\ast ]'.$
(2)
$[\ast ]'$ を示す.
(i)
$n = 3q$ ($q$: $2$ 以上の整数)のとき.
$q$ は素因数を持つから, $n$ は素数でなく, $[\ast ]'$ は真である.
(ii)
$n = 3q+1$ ($q$: $0$ 以上の整数)のとき.
$q = 0$ のとき, $n = 1$ は素数でないから, $[\ast ]'$ は真である.
$q \geqq 1$ のとき, $$n+2 = 3q+3 = 3(q+1)$$ で, $2$ 以上の整数 $q+1$ は素因数を持つから, $n+2$ は素数でなく, $[\ast ]'$ は真である.
(iii)
$n = 3q+2$ ($q$: $0$ 以上の整数)のとき.
$q = 0$ のとき, $n+2 = 4$ は素数でないから, $[\ast ]'$ は真である.
$q \geqq 1$ のとき, $$n+4 = 3q+6 = 3(q+2)$$ で, $3$ 以上の整数 $q+2$ は素因数を持つから, $n+4$ は素数でなく, $[\ast ]'$ は真である.
(i)~(iii) より $[\ast ]$ の対偶 $[\ast ]'$ は真だから, 元の命題 $[\ast ]$ も真である.

問題≪素数の性質≫

 $0$ でない任意の整数 $a,$ $b$ と素数 $p$ に対して, $ab$ が $p$ の倍数ならば $a$ または $b$ は $p$ の倍数であることを示せ.

解答例

 素因数分解の一意性より,
$a = p^{m}a',$ $b = p^nb'$
($m,$ $n$: 非負整数, $a',$ $b'$: $p$ と互いに素な整数)
と書ける. このとき, \[ ab = p^{m+n}a'b'.\] よって, $ab$ が $p$ の倍数ならば, $m+n > 0$ となるから, $m > 0$ または $n > 0$ となり, $a$ または $b$ は $p$ の倍数となる.

問題≪$n!$ の $p$ 進付値≫

 $0$ でない整数 $a$ が $2$ で割り切れる回数の最大値を $v(a)$ で表す.
(1)
$0$ でない任意の整数 $a,$ $b$ に対して, $v(ab) = v(a)+v(b)$ が成り立つことを示せ.
(2)
任意の整数 $m,$ $n$ に対して, $m \leqq n \Longrightarrow v(m!) \leqq v(n!)$ が成り立つことを示せ.
(3)
任意の正整数 $r$ に対して, $v(2^r!) = 2^r-1$ が成り立つことを示せ.
(4)
$v(n!) = 97$ であるような正の偶数 $n$ の値を求めよ.
次の公式は, 証明なしに用いて良い. \[ 2^r \leqq n < 2^{r+1} \Longrightarrow v(n!) = \left[\frac{n}{2}\right] +\dots +\left[\frac{n}{2^r}\right] \quad \cdots [\ast ].\] ここで, 有理数 $x$ 以下の最大の整数を $[x]$ で表す.

解答例

(1)
素因数分解の一意性より
$a = 2^{v(a)}a',$ $b = 2^{v(b)}b'$ ($a',$ $b'$: 奇数)
と表せて
$ab = 2^{v(a)+v(b)}a'b'$ ($a'b'$: 奇数)
となるから, \[v(ab) = v(a)+v(b).\]
(2)
$m \leqq n$ ならば, (1) より \begin{align*} &v(m!) = v(m)+\dots +v(1) \\ &\leqq v(n)+\dots +v(m)+\dots +v(1) = v(n!). \end{align*}
(3)
$[\ast ]$ より, \begin{align*} v(2^r!) &= \left[\frac{2^r}{2}\right] +\dots +\left[\frac{2^r}{2^r}\right] = 2^{r-1}+\dots +1 \\ &= \frac{1(2^r-1)}{2-1} = 2^r-1. \end{align*}
(4)
\[ 2^6-1 < 97 < 2^7-1\] だから, (3) と条件より \[v(2^6!) < v(n!) < v(2^7!).\] よって, (2) の対偶より, $2^6 < n < 2^7.$ そこで, $n$ と $(2^6+2^7)/2 = 96$ の大小を比較してみると, $[\ast ]$ より \[v(96!) = \left[\frac{96}{2}\right] +\dots +\left[\frac{96}{2^6}\right] = 94 < 97\] となるから, (2) の対偶より $96 < n.$ (1) より \begin{align*} v(97!) &= v(97)+v(96!) = 94, \\ v(98!) &= v(98)+v(97!) = 95, \\ v(99!) &= v(99)+v(98!) = 95, \\ v(100!) &= v(100)+v(99!) = 97 \end{align*} となるから, $n = 100.$

問題≪与えられた個数の約数を持つ最小の正整数≫

 ちょうど $8$ 個の正の約数を持つ最小の正整数を求めよ.

解答例

 正整数 $a$ がちょうど $8$ 個の正の約数を持つとし,
$a = p_1{}^{e_1}\cdots p_r{}^{e_r}$
($p_1,$ $\cdots,$ $p_r$: 相異なる素数, $e_1,$ $\cdots,$ $e_r$: 正整数)
と素因数分解されるとする. $a$ の正の約数の個数は $(e_1+1)\cdots (e_r+1) = 8$ であり, 各番号 $k$ に対して $e_k+1 \geqq 2$ であるから, $r \leqq 3$ でなければならない.
(i)
$r = 1$ のとき, $e_1+1 = 8$ より, $e_1 = 7.$ よって, $r = 1$ なる最小の正整数 $a$ は, $a = 2^7 = 128.$
(ii)
$r = 2$ のとき, $(e_1+1)(e_2+1) = 8$ より, $\{ e_1+1,\ e_2+1\} = \{ 4,\ 2\}$ だから, $\{ e_1,\ e_2\} = \{ 3,\ 1\}.$ $p_1p_2{}^3-p_1{}^3p_2 = p_1p_2(p_1+p_2)(p_2-p_1)$ より, $p_1 < p_2 \iff p_1{}^3p_2 < p_1p_2{}^3.$ よって, $r = 2$ なる最小の正整数 $a$ は, $a = 2^3\cdot 3 = 24.$
(iii)
$r = 3$ のとき, $(e_1+1)(e_2+1)(e_3+1) = 8$ より, $e_1 = e_2 = e_3 = 1.$ よって, $r = 3$ なる最小の正整数 $a$ は, $a = 2\cdot 3\cdot 5 = 30.$
(i)~(iii) より, 求める正整数は, $24.$

問題≪正の約数の個数の偶奇≫

(1)
正整数 $a$ の正の約数の個数 $d(a)$ が奇数であるための必要十分条件を求めよ.
(2)
$d(a)$ が偶数である $1$ 以上 $100$ 以下の整数 $a$ の総数を求めよ.

解答例

(1)
$a$ の素因数分解を
$a = p_1{}^{e_1}\cdots p_r{}^{e_r}$ ($p_1,$ $\cdots,$ $p_r$: 素数, $e_1,$ $\cdots,$ $e_r$: 正整数)
とする. このとき, $a$ の正の約数の個数 $d(a)$ は \[ d(a) = (e_1+1)\cdots (e_r+1)\] だから,
$d(a)$ は奇数 $\iff$ $e_1+1,$ $\cdots,$ $e_r+1$ は奇数
$\iff$ $e_1,$ $\cdots,$ $e_r$ は偶数 $\iff$ $a$ は平方数.
ゆえに, $d(a)$ が奇数であるための必要十分条件は, $a$ が平方数であること.
(2)
$1$ 以上 $100$ 以下の整数 $a$ のうち, $d(a)$ が奇数であるものは, 平方数 $1 = 1^2,$ $\cdots,$ $10^2 = 100$ で, ちょうど $10$ 個ある.
ゆえに, $1$ 以上 $100$ 以下の整数 $a$ のうち $d(a)$ が偶数であるものの総数は, \[ 100-10 = 90.\]

問題≪$p^q+q^p$ の形の素数≫

 素数 $p,$ $q$ を用いて $p^q+q^p$ の形に表される素数をすべて求めよ.
[京都大 2016]

解答例

 $p,$ $q$ が素数であり, $p^q+q^p$ も素数であるとする. $p \leqq q$ として一般性を失わない. $p,$ $q$ が奇数のとき, $p^q+q^p$ は $18$ 以上の偶数となってしまうから, $p = 2$ である. そこで, 素数 $q$ に対して $2^q+q^2$ が素数となる条件を求める.
(i)
$2^3+3^2 = 17$ は素数である.
(ii)
$q = 3d+1$ ($d$: 整数)のとき. $q$ は奇数だから, $d$ は偶数である. よって, \begin{align*} 2^q+q^2 &= 2^{3d+1}+(3d+1)^2 \\ &= 8^d\cdot 2+(9d^2+6d+1) \\ &\equiv (-1)^d(-1)+1 = 0 \pmod 3 \end{align*} となり, $2^q+q^2$ は $3$ より大きい $3$ の倍数で素数ではない.
(iii)
$q = 3d+2$ ($d$: 整数)のとき. $q$ は奇数だから $d$ は奇数である. よって, \begin{align*} 2^q+q^2 &= 2^{3d+2}+(3d+2)^2 \\ &= 8^d\cdot 4+(9d^2+12d+4) \\ &\equiv (-1)^d\cdot 1+1 = 0 \pmod 3 \end{align*} となり, $2^q+q^2$ は $3$ より大きい $3$ の倍数で素数ではない.
(i)~(iii) から, 条件を満たす素数は $17$ に限る.

解説

 $p$ と $q$ にいくつかの素数を代入して確かめてみなければ, このような解答にたどり着くことはできないだろう. 自分で証明の方針を立てなければならないという点で, 問題解決能力が試される良問と言える. 難関大学受験者は, このような問題が出題されても対処できるように, よく過去問を解いておきたい.

問題≪平方の和が積で割り切れるための条件≫

 $a,$ $b$ を $2$ 以上の整数とする. $a^2+b^2$ が $ab$ で割り切れるならば, $a = b$ であることを示せ.
[1997 春トーナメント・オブ・タウンズ]

解答例

 $a^2+b^2$ が $ab$ で割り切れるとする. $p$ を $a$ の素因数とする. $p$ は, $ab$ の約数であるから, 仮定により $a^2+b^2$ の約数である. よって, $p$ は $b$ の素因数でもある. $a,$ $b$ の素因数分解における $p$ の指数を $m,$ $n$ とおく. $m \leqq n$ を仮定しても一般性を失わない. このとき, $p^{m+n}$ は $ab$ の約数であり, したがって $a^2+b^2$ の約数である. 一方, $p^{2m+1}$ は $a^2+b^2$ の約数である. よって, $m+n < 2m+1$ が成り立つので, $m \leqq n < m+1$ が得られる. これは $m = n$ が成り立つことを意味する. $p$ は $a,$ $b$ の任意の素因数であるから, $a = b$ が成り立つ.

その他

問題≪星型正多角形の個数≫

 正六十角形の頂点 $\mathrm P_0$ を発着点として右回りに長さがすべて等しい対角線をつなげていくことで描ける図形のうち, 全頂点を通る図形の個数を求めよ.

解答例

 正六十角形 $\mathrm P_0\cdots\mathrm P_{59}$ の頂点 $\mathrm P_0$ を出発点として右回りに長さが $\mathrm P_0\mathrm P_m$ の対角線を $60$ 本つなげていくことで描ける図形を $F_m$ で表す.
(参考: 正十二角形の場合)
$F_m = F_{60-m}$ だから, $1$ 本目の対角線を $\mathrm P_0\mathrm P_m$ ($0 < m < 30$) として数えて良い.
$k$ 本目の対角線は, $km$ を $60$ で割った余りを $r_k$ とおくと, $\mathrm P_{r_{k-1}}\mathrm P_{r_k}$ と表せる.
$m$ が $60$ と互いに素なとき, $r_0,$ $\cdots,$ $r_{59}$ はすべて異なるので, $F_m$ は全頂点を通る.
($0 \leqq i \leqq j < 60,$ $r_i = r_j$ ならば $0 \leqq m(j-i) < 60$ は $60$ の倍数となるから, $m(j-i) = 0$ すなわち $i = j$ となる.)
逆に, $m$ が $60$ の最大公約数が $g \neq 1$ のとき, $F_m$ は点 $\mathrm P_{kg}$ $( 0 \leqq k < 60/g)$ しか通らず, 全頂点を通らない.
よって, $F_m$ が全頂点を通るためには, $m$ が $60$ と互いに素であることが必要十分である.
$60 = 2^2\cdot 3\cdot 5$ と互いに素な $30$ 以下の正整数は $1,$ $7,$ $11,$ $13,$ $17,$ $19,$ $23,$ $29$ の $8$ 個だから, 求める個数は $8.$

解説

 オイラーの $\varphi$ 関数(Euler's phi function)に関する場合の数の問題. 与えられた正整数 $n$ と互いに素な $n$ 以下の正整数の個数を $\varphi (n)$ で表す. オイラーの関数については, 次の等式が有名である.
  • 互いに素な任意の正整数 $m,$ $n$ に対して, \[\varphi (mn) = \varphi (m)\varphi (n).\]
  • 正整数 $n$ の素因数分解が $n = p_1{}^{e_1}\cdots p_r{}^{e_r}$ のとき,
    $\varphi (n) = n(1-p_1{}^{-1})\cdots (1-p_r{}^{-1}).$ (検算に便利)

問題≪$n$ が $(n-1)!$ を割り切る条件≫

 $n$ を $2$ 以上の自然数とする.
(1)
$n$ が素数または $4$ のとき, $(n-1)!$ は $n$ で割り切れないことを示せ.
(2)
$n$ が素数でなくかつ $4$ でもないとき, $(n-1)!$ は $n$ で割り切れることを示せ.
[2016 東工大]

解答例

 準備中.