情報数学 Ⅰ 配布日時 2014 年 5 月 12 日以下に、2 つの整数が互いにあることに関連するいくつかの重要な性質を，定理としてまとめる。特に次の Theorem 1.11 は，『整数論の基本定理』の証明で重要となる。定理 1.11 (ユークリッド) a, b, c  Z に対して、 a | bc かつ (a, b)  1  a | c 証明定理 1.8 より (ac, bc)  c (a, b)  c であり、 a | ac は明らかである。なので、 a | bc より、 a は (ac, bc) を割り切るので、系 1.7 より a | c 。 ■ 定理 1.12 (ユークリッド) a, b, c  Z に対して、 (i) (a, b)  (a, c)  1  (a, bc)  1 (ii) a | c かつ b | c かつ (a, b)  1  ab | c 証明 (i) 定理 1.10 により、ある s, t , u, v  Z が存在して sa  tb  1, ua  vc  1 が成り立つ。従って tb  vc  (1  sa) (1  ua)  1  (s  u  s u)a が成り立ち、 s  u  sua  k とすれば ka  tvbc  1 であるから、 1  L(a, bc) となる。つまり、 a と b c の線形結合が 1 を含むので定理 1.10 より a と b c は互いに素 (a, bc)  1 である。 (ii) a | c なので、 k  Z で c  ka となる。 b | ka であり、かつ (a, b)  1 であるから、b | k となるので、l  Z で k  lb となる。従って、c  lab であるから、ab | c となり、示された。■ 最大公約数 GCD の双対的な概念として最小公倍数があるが、これに関しては必要があるときに、言及することにする。１．３整数についての補足とユークリッドのアルゴリズム整数は実数などと違い離散的である。以下は、大学入試にも登場するような内容も含んでいる。【平方数】平方数とは、ある整数の 2 乗（平方）で表される整数のことである。四角数とは、多角数の一種で、正方形の形に点を並べたときにそこに並ぶ点の総数に合致する整数のことである。表現が異なるが、実際には 2 つの概念は一致する。定義より最小の平方数は 0 2  0 であり、平方数は無限にある。 21 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日例えば 16 は、1 つの辺に点を 4 つ並べて正方形を作ったときに該当するので平方数の 1 つである。『平方数による表現とトリビア』・全ての自然数は、高々4 個の平方数の和で表される。（四平方定理）・全ての自然数は、平方数と偶数の平方数と三角数との和で表される。（多角数定理）三角数： n 番目の三角数を Tn とすると、 Tn  1  2  3    n  n (n 1) 2 ( n 1 ) ・全ての自然数は、平方数と 2 個の三角数との和で表される。（多角数定理）・ 4k 1 の形の素数は 2 個の平方数の和で表される。（二個の平方数の和）・0, 1 以外の平方数は合成数であり、約数を奇数個持つ。 1 2  である。（ゼータ関数、バーゼル問題）  2 6 k 1 k  ・0 を除く平方数の逆数の総和は・ n 2 と (n 1) 2 の間に必ず素数があるかは、証明されていない。だが、素数であるか 2 個の素数の積である数が存在することは、1975 年に陳景潤によって証明されている。 1～4, 4～9, 9～16, 16～25, 25～36, 36～49, 49～64, … ・平方数は、完全数になりえないことが分かっている。・フィボナッチ数のうち平方数であるのは 0 と 1 と 144 のみである。・平方数は 2 つの連続した三角数の和として表される。・十の位が奇数の場合は、一の位は必ず 6 になる。16, 36, 196, 256 など。・下 2 桁が 25 の場合は、百の位は必ず、0, 2, 6 のいずれかになる（5 番目の平方数である 25 の場合、百の位は 0 と見なす）。25, 225, 625, 1225 など。・144 と 441、169 と 196 と 961、256 と 625、1024 と 2401 のように、数字を並べ替えただけで、別の平方数になるものが多い。 22 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日離散性の例１： n, mZ とするとき、次のことがいえる。 m  n  m 1  m  n  m2  n  m 1 m  n  m 1  nm nm  n  m 1 矛盾 ■ 離散性の例２：「１以上の連続する２つの整数の積に１を加えた数は平方数にはならない」 ∵ f (n )  n ( n 1) 1 ( n 1 ) が平方数とはならない。 n 1 のとき、 f (n )  ( n 1) 2   n  0 f (n )  n 2  n  1  0 なので、 n 2  f (n )  ( n 1) 2 となるので、 f (n) は平方数とはならない。 ■ 注意）不思議なことかもしれないが、1 以上の連続する 4 整数の積に 1 を加えた数は常に平方数になる． n (n 1) (n  2 ) (n  3)  1  (n 2  3n 1) 2 離散性の例３： n の倍数は幅 n ごとにトビトビに存在する。つまり、適当に連続する n 個の整数をとれば、その中には必ず n の倍数が 1 個存在する。また余りの均等性より、連続する n 個の整数の中には n で割ったときの余りが、 1, 2, 3, , n  1 になる整数が 1 つずつ存在する。 ■ 離散性の例４： n を自然数とする。 a が n の倍数のとき、 n  a  n  a 0 ■ 離散性の例５：一般に、 k を 2 以上の自然数とするとき、連続する k 個の整数の中には， k の倍数、 k 1 の倍数，…, 2 の倍数が必ず存在する。したがって、連続する k 個の整数の積は必ず k! の倍数になる。 ■ 注意) 連続する k 個の整数の積は必ず k! の倍数になることの証明はいろいろ考えられるが、次の二項係数の式を見れば、一目瞭然であろう(分子が連続する k 個の整数で、二項係数 n C k は整数だから)。 n Ck   n! (n  k ) ! k ! n (n 1) (n  2 )  ( n  k  1) k! 23 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日離散性の例６：奇数の 2 乗は 8 で割ると 1 余る数である。 ∵ (2k 1) 2  4 k 2  4 k 1  4 k (k 1)  1 k ( k 1) は連続 2 整数の積だから 2 の倍数なので、 4k ( k 1) は 8 の倍数である。よって、奇数の 2 乗は 8 で割ると 1 余る数である。 ■ 離散性の例７： n  3 とする。 n と n  2 が共に素数のとき、 n  1 は 6 の倍数であることを示せ。 ∵ n  3 で n と n  2 が共に素数だから、n と n  2 は共に奇数である。よって、n  1 は偶数となる。また、 n, n  1, n  2 は連続 3 整数だから、このうち 1 つは必ず 3 の倍数となる。n  3 で n と n  2 が共に素数だから、これらが 3 の倍数になることはなく、n  1 が 3 の倍数になる。したがって、 n  1 は 2 の倍数かつ 3 の倍数になるので，6 の倍数である。 ■ 【別解】連続する 6 整数は 6m  2, 6m 1, 6m, 6m 1, 6m  2, 6m  3 と表現できる。この中で、 6m  2 と 6m  2 は 2 の倍数、 6m  3 は 3 の倍数、 6m は 6 の倍数になるので、 n  3 で n と n  2 が共に素数になるとき、 n  6m 1, n  2  6m 1 になるしかないので、その間の数 n  1 が 6m 、つまり 6 の倍数になる。 ■ 注） n と n  2 が共に素数のとき、この 2 つの素数を双子素数と呼ぶ。双子素数は (3, 5), (5, 7), (11, 13), … など、無限に存在すると考えられているが、未だ証明されていない。上の例は、(3, 5) 以外の双子素数の間の数は必ず 6 の倍数であることを主張している。 2 n  1 と 2 n  1 が共に素数となる自然数 n をすべて求めよ。 n n n ∵ 2  1 、 2 、 2  1 は連続する 3 整数であることに注目する。 n  1 のとき、2 n 1  3 であるので、2 n  1 と 2 n  1 が共に素数のとき、離散性の例７より、 2 n は 6 の倍数にならねばならないが、これは矛盾である。 n n よって、 2  1 と 2  1 が共に素数となる自然数は n  1 の場合のみである。離散性の例８： ■ 24 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日 25 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日。。。。 26 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日・・・ 27 情報数学 Ⅰ 配布日時 2014 年 5 月 12 日・・・・・・ 28