整数の基本1：約数・倍数関係

はじめに

今回は整数の基本3ヶ条の1つ目，約数・倍数関係について解説していきます．

（3ヶ条の記事を読んでいない場合はこちら(click!)から．）

整数問題では圧倒的に多く使われる方法で，避けては通れないところです．

「素因数分解の一意性」を使って「整数を絞り込む」ことを意識して，読み進めていってください．

約数・倍数関係の利用

まずは以下の例題を解いてみてください．

さて，どのように考えたでしょうか．

注目して欲しいのは，（明らかに強調されていますが）右辺が「約数の分かる値」であること．

右辺が「約数の分かる値」ということは，素因数が全て分かっているということです．（逆に言えば，素因数が分からない数の約数は分かりません．）

整数に関する等式なので，素因数分解の一意性から，左辺と右辺が等しければ，素因数分解した形も等しいはず．ここから$x,y$を絞り込んでいきます．

具体的に見ていきましょう．
(1)の$12$の素因数は$2,2,3$です．

左辺を因数分解すると$(x-y)(x+y)$となりますから，この２つの因数に先ほどの$2,2,3$を割り当てられるはずです．このことを素因数分解の一意性が保証しています．

(2)以降も同じように進めていきます．右辺の素因数を左辺の因数（今回は全て同じで$x-y$と$x+y$です）に分配するのですね．

ここで一つ注意点を．

2次不定方程式の記事でも説明はするつもりですが，素因数を分配するときに工夫しておくとよいことがあります．

それは，大小（＋正負）と偶奇です．

例えば(1)に関して，$x,y$が整数だったとしましょう．
すると，$x-y,x+y$の候補は以下のようになります．

プラスマイナスに加え，入れ替えもあって非常に煩雑ですね．

今回は$x,y$が自然数であるため，符号はプラスのみを選べばよいです．

さらに、2数の差が$2y$と偶数であるため，偶奇は一致し，$(1,12),$や$(34),$といった組は不適であると分かります．（実際に計算すると$x,y$が整数となりませんね）

不要な計算はミスの元になります．大小と偶奇に関して工夫をすることで，上手に計算を進めましょう．

略解になりますが解答を載せておきます．

整数の等式が与えられ，約数・倍数関係を利用するときは

（整数の積）=（約数の分かる値）
の形を目指すことにより，左辺の因数分解された各要素が，右辺の約数として絞り込まれます．

もし，$x^2-y^2=n$（$n$は整数）という式であれば，$n$がどう分解されるのか分からないため，$x,y$の候補が絞れていません．（$x-y,x+y$がnの約数であることは分かりますが，そこからの進展がない，ということです．）

両辺は整数の式にしましょう．
分数があるなら分母を払い，ルートは二乗して外しておかなければ，約数の話ができなくなります．

上に挙げたように，「約数の分かる値」には

定数・素数・素因数分解された数が挙げられます．

このまま３つを覚えてもらってもいいですが，定数や素数も大きなくくりでは素因数分解された数です．

「素因数」が全て分かる=約数・倍数関係が分かる
約数・倍数関係は，「素因数」の分配である

と認識しておきましょう．

まとめ