足跡-sokuseki-

りかの日進月歩の記録

「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である

数学証明

根号のついた様々な数が無理数であることを示すのが最近の趣味です。
その証明に使う補題(のようなもの)を証明したいと思います。

証明内容はタイトルにも書いた通り、

『 $a,n$ が正の整数、 $p$ が素数のとき、

$a^n$ が $p$ の倍数 $\Longleftrightarrow a$ が $p$ の倍数』

です。必要条件と十分条件に分けて証明していきたいと思います。

⑴『 $a^n$ が $p$ の倍数 $\Longleftarrow a$ が $p$ の倍数』を示す

$t$ を整数として、 $a=pt$ とおきます。このとき

$a^n = (pt)^n = p^n t^n$

$p^n t^n$ は $p$ の倍数なので、 $a^n$ が $p$ の倍数であることがわかります。

よって必要条件は示すことができました。

⑵『 $a^n$ が $p$ の倍数 $\Longrightarrow a$ が $p$ の倍数』を示す

これを直接証明することは難しいので、対偶を示すことにします。

『 $a^n$ が $p$ の倍数 $\Longrightarrow a$ が $p$ の倍数』の対偶は

『 $a$ が $p$ の倍数でない $\Longrightarrow a^n$ が $p$ の倍数でない』……(＊) です。

なので、(＊)を数学的帰納法を使って示します。

(i) まずは $n=1$ のとき

「 $a$ が $p$ の倍数でないならば $a$ が $p$ の倍数でない」は自明なので(＊)は成り立ちます。

(ii) 次に、 $n=k$ のときに(＊)が成り立つと仮定します。

このとき仮定より、「 $a$ が $p$ の倍数でないならば、 $a^k$ が $p$ の倍数でない」といえます。

またこのとき、

「 $p$ の倍数でない数に、 $p$ の倍数でない数をかけても $p$ の倍数にはならない」……(A)

ということがいえるならば、

$p$ の倍数でない $a^k$ に、 $p$ の倍数でない $a$ をかけた $a^{k+1}$ も $p$ の倍数ではありません。

よって(A)さえ示すことができれば、 $n=k+1$ のときも(＊)が成り立つといえます。

ここで(A)を示すために、 $p$ の倍数でない2数の積を $p$ で割ったあまりについて考えます。

(ここでは合同式を使って、整数 $a$ を整数 $p$ で割ったあまりと、整数 $b$ を整数 $p$ で割ったあまりが等しいとき
「 $a \equiv b$ ( mod $p$ ) 」と表すことにします。 )

整数 $a, b, c, d$ を用いて、 $p$ の倍数でない2数を

$ap+b$ 、 $cp+d$ 　　(ただし、 $0 \leq a, c$ かつ $0 < b, d < p$ )

とします。

この2数の積を $p$ で割ったあまりは

$(ap+b)(cp+d) \equiv acp^2 + ( ad+bc ) p + bd \equiv bd$ 　 ( mod $p$ )

と表せます。

ここで、「 $bd \equiv 0$ 　( mod $p$ ) 」と仮定すると、

$bd$ は $p$ の倍数であり、 $p$ は素数なので、

$b$ と $d$ の少なくとも片方が「 0 または $p$ の倍数」である必要があります。

しかし、 $0 < b, d < p$ より、

$b$ と $d$ の両方ともが 0 でも $p$ の倍数でもないので、これは矛盾します。

よって「 $bd \equiv 0$ 　( mod $p$ ) 」という仮定が間違っていることがわかります。

以上より $bd \not\equiv 0$ 　( mod $p$ ) となります。

よって、 $(ap+b)(cp+d) \not\equiv 0$ 　( mod $p$ ) となり、

$p$ の倍数でない2数の積は $p$ の倍数でないことが示せました。(A)の証明はこれで終了です。

これで、

(i) $n=1$ のとき(＊)が成り立つ

(ii) $n=k$ のときに(＊)が成り立つならば、 $n=k+1$ のときに(＊)が成り立つ

を示すことができたので、数学的帰納法より(＊)を証明することができました。

対偶である(＊)を証明することができたので、

『 $a^n$ が $p$ の倍数 $\Longrightarrow a$ が $p$ の倍数』が成り立つことが証明できたことになります。

よって、必要条件、十分条件ともに成り立つことがわかったので、

『 $a,n$ が正の整数、 $p$ が素数のとき、 $a^n$ が $p$ の倍数 $\Longleftrightarrow a$ が $p$ の倍数』

を証明することができました。

ところでこの証明、名前ついてたりするんですかね……。有名な気がするんですが……。

参考サイト

合同式の意味とよく使う６つの性質 | 高校数学の美しい物語

追記

この記事を投稿した後に、@lvbourbakiさんに指摘していただいて気づいたのですが、(A)の証明の部分で合同式を使って式変形をする必要はありませんでした。
ということで、簡潔になった(A)の証明を以下に書きます。

$p$ の倍数でない2つの自然数を $a, b$ とします。

ここで、「 $ab$ が $p$ の倍数である」と仮定すると、 $p$ は素数なので、

$a$ と $b$ の少なくとも片方が「 0 または $p$ の倍数」である必要があります。

しかし、 $a$ と $b$ の両方ともが 0 でも $p$ の倍数でもないので、これは矛盾します。

よって「 $ab$ が $p$ の倍数である」という仮定が間違っていることがわかります。

以上より $ab$ は $p$ の倍数でないということがいえるので、

$p$ の倍数でない2数の積は $p$ の倍数でないことが示せました。

~~じ、自明だ……~~

ということで随分と短くなりました。

@lvbourbakiさん、どうもありがとうございました。