互いに素の証明

上野竜生です。倍数・約数の確認と「互いに素」の定義、証明を紹介します。

「互いに素」の証明

スポンサーリンク

<基本>倍数・約数

自然数NがN=nd(n,dは整数)というように積の形でおけるときNはdの倍数といい、dはNの約数という。

自然数N,MがN=dn , M=dmのようにかけるとき、共通の約数dのことを公約数という。

1以外に正の公約数dをもたないときNとMは互いに素という。
(±1以外に公約数をもたないとき と定義してもよいし,2以上の公約数をもたない でもよい。)

たとえばnが6の倍数と言われればn=6n’ (n’は整数)とおくことができます。

互いに素の基本性質

nとn+1は互いに素である。

「互いに素」の証明は少し難しいと感じるかもしれません。1以外に公約数をもたないことを直接証明するのは難しいので通常は背理法を使います。また「○○が互いに素ならば△△も互いに素であること」の証明だったら対偶をとることもできますね。直接示すのは難しいという認識を持っておきましょう。

[証明] 

nとn+1が2以上の公約数dを持つと仮定する

n=ad
n+1=bd(a,b,dは整数。d≧2)とかける。

第2式から第1式をひくと

1=(b-a)d

となるからdは1の約数。しかしdは2以上なので矛盾。よってnとn+1は互いに素。

この程度なら直接でも示せそうですが互いに素の基本に従い,背理法を使いました。

この結果を利用すると

nとn+dの公約数はdの約数以外にはないということがわかります。(dの約数すべてが公約数とは限らない。反例n=5, d=2)

例題1:○と△は互いに素を示す

nが偶数のとき、n+3とn2+n+2は互いに素であることを証明せよ。

nが偶数(=2の倍数)なのでn=2kとおけます。まずはそこから整理してみましょう。

答えnが偶数のときn=2k(kは整数)とおける。
n+3=2k+3,
n2+n+2=4k2+2k+2である。2k+3と4k2+2k+2が2以上の公約数dをもつと仮定する。
2k+3=ad   ・・・①
4k2+2k+2=bd ・・・②(a,b,dは整数。d≧2)とおける。
②-(①×2k)より
-4k+2=(b-2ak)d・・・③
③+①×2より
8=(b-2ak+2a)d
dは8の約数で2以上だからd=2またはd=4
しかしd=2または4のとき①の左辺は奇数であるが右辺は偶数であるから矛盾。
よって2以上の公約数dはもたず,互いに素である。

例題2:○と△が互いに素ならば◎と▽も互いに素を示す

自然数nとmに対し次を示せ。
nとmが互いに素 ⇔ n2とm2が互いに素

示すものは

① nとmが互いに素 ⇒ n2とm2が互いに素

② n2とm2が互いに素 ⇒ nとmが互いに素

ですが、どちらも直接互いに素を示すのは大変(2以上の公約数をもたないことの証明は大変)なので背理法でもいいですが高校生にとって「AならばB」の否定がやや難しい(「AならばB」の否定は「AであるがBではない」です)ので対偶のほうがわかりやすいでしょう。

①②ともに対偶で示します。②のほうが楽です。

答え示すべきものは

ア) nとmが互いに素 ⇒ n2とm2が互いに素

イ) n2とm2が互いに素 ⇒ nとmは互いに素

であるがどちらも対偶で示す。つまり
ア’) n2とm2が2以上の公約数dをもつ ⇒ nとmが2以上の公約数をもつ

イ’) nとmが2以上の公約数dをもつ ⇒ n2とm2が2以上の公約数をもつ
を示せば良い。 イ’)について
n=ad , m=bd (a,b,dは整数。d≧2)とおける。このとき
n2=a2d2 , m2=b2d2なのでn2,m2は公約数d2をもつ。
d≧2なのでd2≧4≧2であり,イ’)は成立。

残る部分はア’)ですが少し難しいです。最初の置き方にひと工夫したいところです。

n2=sd , m2=td (s,t,dは整数。d≧2)とおける。このときn,mは公約数dをもつ。

と言えればいいのですがそうはいきません。たとえばn2が4の倍数でもnは2の倍数としかいえません。だからといってdが平方数とも限らないので公約数(√d)をもつともいえません。

そこでdをさらに(素因数)分解し,dを素数としてやりましょう。素数ならば先ほどの言いたいことが言えます。この発想は初見ではなかなか難しいので勉強しておきましょう。

答えア’)について(最大とは限らない素数の)公約数pをもつとする。
n2=sp , m2=tp (s,tは整数。pは素数)とおける。
するとn,mはともにpの倍数となるからnとmは公約数pをもつ。
よってア’)は成立。以上より
nとmが互いに素 ⇔ n2とm2が互いに素
が成り立つ。
nとmが2以上の公約数dをもつ と仮定することはできます。
2以上の整数は素数か合成数(a×bの形にかける数)のどちらかです。
dが最初から素数のときはp=dとすれば↑の答案がそのまま使えます。
dが合成数の時はdを素因数分解すると素数の積の形でかけるので,その中に現れる素数をpとおけば↑の答案が使えます。
つまり互いに素であることを式で表現するとき
公約数dを2以上の整数ではなく、素数とおくことができます。(もちろん「最大」公約数とは限らない)
素数の性質として
「ABがpの倍数ならばAがpの倍数またはBがpの倍数」
が成り立ちます。これにA=B=nを代入すると
「n2がpの倍数ならばnはpの倍数」がいえます。
テストでもしア’)がわからなかったとして、そこで諦めずわかりやすいイ’)だけでも答案に残しましょう。特に同値命題の証明では片側がわからなくてももう片方は簡単かもしれません。先に示そうとしたのがたまたま難しいほうだからと言ってそこで諦めたら損です。

「互いに素」の証明は意外と盲点です。他の受験生と差をつけるためにやっておきましょう。難関大でもたまに出てきます。

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする