前回の記事
の続きです。
1. ユークリッドの互除法の応用例
1-1. 一次不定方程式 ax + by = c の整数解
大学入試などで頻出のテーマです。前回の記事の 3 章で詳しく書いてみました。
1-2. 最小公倍数を求める
整数 $a$, $b$ の最大公約数が求まったら最小公倍数は簡単に求められます。最小公倍数を ${\rm lcm}(a, b)$ と表すと
$ab = {\rm gcd}(a, b) {\rm lcm}(a, b)$
が成立します。理由は簡単で、$d = {\rm gcd}(a, b)$ とおくと
$a = da'$
$b = db'$
とすると、$a'$ と $b'$ は互いに素になるので、${\rm lcm}(a, b) = da'b'$ になります。よって、
${\rm gcd}(a, b) {\rm lcm}(a, b) = (da'b')d = (da')(db') = ab$
となります。したがって、最大公約数が求まっていたら最小公倍数は
${\rm lcm}(a, b) = ab / {\rm gcd}(a, b)$
によって計算することができます。これをプログラムにする上での注意点としては、$ab$ の計算で long long 型オーバーフローする危険性があるので、以下のようにすると無難です。$a$ は $GCD(a, b)$ で割り切れることが保証されているので、先に $a$ を $GCD(a, b)$ で割っています。
/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
if (b == 0) return a;
else return GCD(b, a % b);
}
/* a と b の最小公倍数を求める */
long long LCM(long long a, long long b) {
long long g = GCD(a, b);
return a / g * b;
}
1-3. 3 個以上の整数の最大公約数・最小公倍数を求める
$a, b, c$ の最大公約数・最小公倍数を考えます。実は簡単で
- ${\rm gcd}(a, b, c) = {\rm gcd}({\rm gcd}(a, b), c)$
- ${\rm lcm}(a, b, c) = {\rm lcm}({\rm lcm}(a, b), c)$
が成立するので、最初に $a$ と $b$ の最大公約数・最小公倍数を求めてから、それと $c$ との最大公約数・最小公倍数を求めればよいです。4 個以上になっても同様です。
1-4. n と n+1 は互いに素
大学受験において頻出の話題です。証明は「ユークリッドの互除法の原理」を思い出すと簡単です。すなわち、${\rm gcd}(a, b) = {\rm gcd}(a-b, b)$ が成り立つことを利用します:
${\rm gcd}(n+1, n) = {\rm gcd}(1, n) = 1$
最後の 1 になるところは、1 の約数は 1 しかないことから従います。
1-5. 東大入試問題 (a^2 - a が 10000 で割り切れるもの)
東京大学 2005 年前期試験の理系第４問・文系第２問で以下のような問題が出題されました。
3 以上 9999 以下の奇数 $a$ で、$a^2 - a$ が 10000 で割り切れるものをすべて求めよ。
【解】
$a(a-1)$ が $10000 = 2^4 × 5^4$ の倍数となるような $a$ を求めます。
上の議論より $a$ と $a-1$ は互いに素であるから、$a$ と $a-1$ とは共通の素因子を持ちません。したがって、
- $a$ は $2^4$ の倍数で、$a-1$ は $5^4$ の倍数
- $a$ は $5^4$ の倍数で、$a-1$ は $2^4$ の倍数
- $a$ は $10^4$ の倍数
- $a-1$ は $10^4$ の倍数
しか可能性がないことがわかります。ここで、$a$ が $9999$ 以下であることから 3 と 4 はありえないです。さらに $a$ が奇数であることから 1 もありえないです。したがって
$a$ は $625$ の倍数で、$a-1$ は $16$ の倍数
ということになります。$a = 625a'$ とおくと、$3 \le a \le 9999$ より、$1 \le a' \le 15$ になります。最悪 $15$ 通り調べればいいのですがもっと楽できます。$a-1$ が $16$ の倍数であることから、
$625a' - 1 ≡ 0$ (${\rm mod}. 16$)
⇔ $a' ≡ 1$ (${\rm mod}. 16$)
となります。よって、$1 \le a' \le 15$ を合わせて考えると、$a' = 1$ しかないです。よって答えは $a = 625$ のみとなります。
(終)
1-6. フィボナッチ数列の隣接する 2 項は互いに素であること
$F_0 = 1, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}$ で表されるフィボナッチ数列についてです。ユークリッドの互除法を用いると
${\rm gcd}(F_{n}, F_{n-1})$
$= {\rm gcd}(F_{n-1} + F_{n-2}, F_{n-1})$
$= {\rm gcd}(F_{n-2}, F_{n-1})$ (${\rm gcd}(a, b) = {\rm gcd}(a-b, b)$ を利用)
$= {\rm gcd}(F_{n-1}, F_{n-2})$
が成立するので、数学的帰納法を用いて証明できそうです。実際
- $n = 1$ のとき、${\rm gcd}(F_{n}, F_{n-1}) = {\rm gcd}(F_1, F_0) = {\rm gcd}(1, 1) = 1$
- ${\rm gcd}(F_{n-1}, F_{n-2}) = 1$ ならば ${\rm gcd}(F_{n}, F_{n-1}) = 1$
が言えるので OK です。
1-7. フェルマー数がすべて互いに素であること
フェルマーは
$n$ を $0$ 以上の整数としたとき、$F_n = 2^{2^n} + 1$ はすべて素数になるのではないか
と予想しました。実は間違っていたことがわかるわけですが、$F_n = 2^{2^n} + 1$ の形で表される整数をフェルマー数、特に素数になっているものをフェルマー素数と呼びます。$n$ が小さい場合は
- $F_0 = 3$
- $F_1 = 5$
- $F_2 = 17$
- $F_3 = 257$
- $F_4 = 65537$
です。ここまでは確かに素数だったのですが、オイラーによって $F_5 = 4294967297 = 641 × 6700417$ と反例が見つかりました。しかしながらフェルマー数については
$n$ と $m$ を相異なる $0$ 以上の整数とする。$2^{2^n} + 1$ と $2^{2^m} + 1$ は互いに素である。
というかなり面白いことが示せます。フィボナッチ数は「隣接する」2 つが互いに素であったのに対し、フェルマー数はどの 2 つも互いに素になっています。一般性を失わず $n > m$ とします。
${\rm gcd}(2^{2^n} + 1, 2^{2^m} + 1)$
を計算します。$n = m + k$ として、ユークリッドの互除法を用いると
${\rm gcd}(2^{2^n} + 1, 2^{2^m} + 1)$
= ${\rm gcd}(2^{2^{m+k}} + 1, 2^{2^m} + 1)$
= ${\rm gcd}(2^{2^m2^k} + 1, 2^{2^m} + 1)$
= ${\rm gcd}((2^{2^m})^{2^k} + 1, 2^{2^m} + 1)$
= ${\rm gcd}((-1)^{2^k} + 1, 2^{2^m} + 1)$ ($2^{2^m} ≡ -1$ (${\rm mod}. 2^{2^m} + 1$) より)
= ${\rm gcd}(2, 2^{2^m} + 1)$
= 1 ($2^{2^m} + 1$ は奇数であることより)
と計算できます。少し入り組んでしまいましたが、相異なるフェルマー数が互いに素であることが示せました。
1-8. 素数が無限にあることの別証明
「素数が無限にあることの証明」もユークリッド原論で示された非常に鮮やかな証明として知られています:
【証明】
任意の素数を $p$ として、$p$ より大きな素数が存在することを示せばよい。$p$ 以下のすべての素数の積に $1$ を加えて
$a = 2 × 3 × 5 × ... × p + 1$
とする。
- $a$ が素数のとき、$a$ は $p$ より大きい素数である
- $a$ が合成数のとき、$a$ は $2, 3, 5, ..., p$ のいずれでも割り切れないので、$a$ の任意の素因子 $q$ は $p$ より大きい。
いずれにしても $p$ より大きな素数を得ることができる。
(証明終)
しかしながら、前節のフェルマー数を利用した鮮やかな別証明方法があります。すなわち、フェルマー数 $F_n = 2^{2^n} + 1$ はどの 2 つも互いに素であることを利用します。どのフェルマー数も少なくとも 1 つの素因子を持っていて、それらはどの 2 つも互いに異なる必要があるため、素数が無限にあることになります。
(別証明終)
1-9. ピタゴラス数を求める 〜 Z[i] 環の整数論 〜
$x^2 + y^2 = z^2$ を満たす整数 $(x, y, z)$ の組をピタゴラス数と呼びます。いわゆるピタゴラスの定理 (三平方の定理) に登場してくる式で、これを満たす $(x, y, z)$ は長さ $z$ の斜辺をもつ直角三角形の三辺の長さになります。最初の考察として、$d = {\rm gcd}(x, y)$ とおくと、$z^2$ は $d^2$ の倍数になるため、$z$ は $d$ の倍数であることが必要です。よって、
$x = dx', y = dy', z = dz'$
とおくと、$x'^2 + y'^2 = z'^2$ になります。すなわち問題は $x$ と $y$ が互いに素である場合に帰着されます。
$x$ と $y$ を互いに素であるとする。$x^2 + y^2 = z^2$ を満たす整数 $(x, y, z)$ は、$m, n$ を整数として
$x = m^2 - n^2$, $y = 2mn$, $z = m^2 + n^2$
で与えられる ($x$ と $y$ を入れ替えたものを含む)。
具体例として、$m = 2$, $n = 1$ とすると、$x = 3, y = 4, z = 5$ と有名な直角三角形が登場します。ピタゴラス数は実は普通の整数論でも導くことができるのですが、整数を拡張して複素整数を考えると明快に導くことができます。
【解】
$x^2 + y^2 = z^2$
⇔ $(x + yi)(x - yi) = z^2$
である。ここからは整数を複素整数 ($x$, $y$ を整数として $x + yi$ で表されるものを複素整数と呼ぶ) に拡張して考える。実は複素整数の世界においても、
- 「割り切れる」「割り切れない」という概念が定義できる
- 「最大公約数」という概念が定義できる
- 「素数 (素元)」という概念が定義できる
- ユークリッドの互除法が成立する
- 素因数分解の一意性が成立する
ということが知られている。$x + yi$ と $x - yi$ とが複素整数の意味で互いに素であることを示す。$\lambda = 1 + i$ とおく。ここで、もし $x + yi$ が $\lambda$ で割り切れると仮定すると、$z^2 = x^2 + y^2 = (x + yi)(x - yi)$ は、$(i + i)(1 - i) = 2$ で割り切れることになってしまう。ここで以下の性質を利用して矛盾を導く:
$a$ を通常の整数の意味での整数とすると、$a$ が奇数のとき $a^2 ≡ 1$ (${\rm mod}. 4 $) で、$a$ が偶数のとき $a^2 ≡ 0$ (${\rm mod}. 4 $) である。
通常の平方数が $4$ で割って $2$ 余ることはありえないので $z^2$ は $4$ の倍数であることになる。しかし、$x$ と $y$ のどちらかは奇数であるから、$x^2 + y^2$ を $4$ で割った余りとしてあり得るのは、$1$ か $2$ のみである。これは矛盾である。
したがって、$x + yi$ が $\lambda$ で割り切れることはない。また実は $\lambda$ は複素整数の世界では素数である。したがって $x + yi$ と $\lambda$ は互いに素である。このことを利用してユークリッドの互除法を適用すると、
${\rm gcd}(x - yi, x + yi)$
= ${\rm gcd}(2x, x + yi)$
= ${\rm gcd}(-i\lambda^2 x, x + yi)$
= ${\rm gcd}(x, x + yi)$ ($x + yi$ と $\lambda$ は互いに素)
= ${\rm gcd}(x, yi)$
= 1 ($x$ と $y$ とは互いに素なため)
となって、$x + yi$ と $x - yi$ とが複素整数の意味で互いに素であることが導かれた。したがって、$(x + yi)(x - yi) = z^2$ より、$x + yi$ と $x - yi$ はともに複素整数の意味で平方数になるので
- $x + yi = (m + ni)^2$
- $x - yi = (m - ni)^2$
と表せる (厳密にはこれに $±1, ±i$ 倍したものを含む)。これを展開することで、
- $x = m^2 - n^2$
- $y = 2mn$
が得られる。
(終)
途中多少入り組みましたが、要するに $x + yi$ と $x - yi$ とが複素整数の意味で互いに素であることを利用するという非常に明快なロジックでした。