logo

最大公約数と互いに素 📂整数論

最大公約数と互いに素

定義 1

  1. 二つの整数 nnm0m \ne 0 について、次を満たす整数 kk が存在するなら、nnmm で割り切れると言う。 n=mk n = mk この時、nnmm倍数multiplemmnn約数divisorと言い、以下のように示す。 mn m \mid n mmnn を割り切れない場合は、取り消し線を引いて mnm \nmid n と表示する。
  2. 00 ではない二つの整数 aabb が与えられているとする。両方を割る約数の中で最も大きな数を aabb最大公約数greatest Common Divisorと言い、gcd(a,b)\gcd (a,b) のように表記する。
  3. もし gcd(a,b)=1\gcd (a,b) = 1 ならば、aabb互いに素relatively Primeであると言う。

説明

最大公約数と互いに素という概念は、ほとんどの人が小学校の時から見てきた概念だ。

互いに素の英語表現である Relatively Primeから分かるように、実際に多くの人の言葉の習慣とは異なり(このポストのタイトルでもスペース無しで互いに素と書いているように)互いに素は、相対的にrelativelyprimeという意味だ。英語で「お互いに」と表現するにはMutuallyという単語がもっと適しているかもしれないが、数学全般でMutuallyにはそれなりに重要な意味があるため、相対的に(Relatively)が使われる。ここでの相対的というのは、二つの数 aabb は、11 以外の約数を共有していないため、お互いに対しては事実上素数と同じ扱いができるという意味だ。絶対的には素数ではないかもしれないが、お互いに対しては素数として扱うことができるという程度に受け取れば良い。

併せて見る

代数学的一般化

一意分解整域にて一般化される。


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p30. ↩︎