skip to content
Site header image satoooh.org

整数問題で使う基本的な性質などをまとめてみる(約数倍数、剰余まわり)

Last Updated:

受験生に教える用にまとめてみます。この記事で紹介するものは示せと言われない限りは基本的に既知として考えてよいと思っています。

おさえておきたい事実

最初におさえておきたい事実を 2 つ紹介します。ここから話を広げてみましょう。

1. a,ba, b の公約数の集合は、ab,ba-b, b の公約数の集合と一致する

ユークリッドの互除法などの元になっている考え方ですね。

💡
基本事実

整数 a,ba, b について、 a,ba, b の公約数は ab,ba-b, b の公約数であり、逆に ab,ba-b, b の公約数は a,ba, b の公約数になる。

集合が一致するので、最大公約数も一致する。

略証

  • SS : a,ba, b の公約数の集合
  • TT : ab,ba-b, b の公約数の集合

とする。

任意の sSs \in S に対して、a,ba, bss で割り切れるので、a=sk,b=sla = sk, b = sl とかける。このとき ab=s(kl)a-b = s(k-l) となるので aba-bss で割り切れる。よって ssab,ba-b, b の公約数であるとも言えるので sTs \in T が成立する。

よって STS \subseteq T が成立。

逆も同様に言えるので、 TST \subseteq S がいえ、結局 S=TS = T が成り立つ。(証明終)

2. ユークリッドの互除法の原理的なやつ

💡
基本事実

整数 a,ba, baba \geq b)の最大公約数を gcd(a,b)gcd (a, b) とする。aabb で割った余りを rr とするとき、次の式が成立する。

gcd(a,b)=gcd(b,r)gcd(a, b) = gcd(b, r)

1の事実から、gcd(a,b)=gcd(ab,b)gcd(a, b) = gcd(a-b, b) が成り立ちます。これを繰り返すと、gcd(a,b)=gcd(ab,b)=...=gcd(akb,b)gcd(a, b) = gcd(a-b, b) = ... = gcd(a-kb, b) となります。

つまり aabb で割った商、余りをそれぞれ k,rk, r とすれば、a=kb+ra = kb + r より gcd(akb,b)=gcd(r,b)gcd(a-kb, b) = gcd(r, b) つまり上の式が言える。

ポイント: どんな2数の最大公約数でも求められる!

  • gcd(a,b)=gcd(b,r1)gcd(a, b) = gcd(b, r_1) : ただし aabb で割った余りを r1r_1 とする
  • gcd(b,r1)=gcd(r1,r2)gcd(b, r_1) = gcd(r_1, r_2) : ただし bbr1r_1 で割った余りを r2r_2 とする
  • ...

と繰り返し割り算をしていくと、あまりの定義からかならず ri=0r_i = 0 を満たす ii が存在することになる。( 0r1<b0 \leq r_1 < b , 0r2<r1,...0 \leq r_2 < r_1, ... と範囲が小さくなっていくので)

ということは、そのような最小の ii について、gcd(a,b)=gcd(ri1,0)=ri1gcd(a, b) = gcd(r_{i-1}, 0) = r_{i-1} を求めてやればこれが最大公約数になる。

整数論の基本定理

💡
整数論の基本定理

整数 a,ba, b が互いに素ならば、ax+by=1ax + by = 1 をみたす整数 x,yx, y が存在する。

略証

aba \geq ba,ba, b は互いに素であるとする。 aabb で割った商と余りを q,rq, r とすれば、a=bq+ra = bq + r が成立。このことから、次のように変形できる。

ax+by=1(bq+r)x+by=1b(qx+y)+rx=1ax + by = 1 \\ \Leftrightarrow (bq + r) x + by = 1 \\ \Leftrightarrow b(qx + y) + rx = 1

つまり、 bX+rY=1bX + rY = 1 なる整数 X,YX, Y が存在すれば、 x=X,y=XqYx = X, y = X - qY と対応付けることで、上式を満たす整数 x,yx, y を構築できたことになる。

以上の議論から、示すべき条件は次のように変形できる。

  • ax+by=1ax + by = 1 をみたす整数 x,yx, y が存在
  • bx+ry=1\Leftrightarrow bx + ry = 1 をみたす整数 x,yx, y が存在

この操作を繰り返す。つまり、ri=0r_i = 0 (この ii の存在は上で既に示してある)として、

gcd(a,b)=gcd(b,r1)=...=gcd(ri1,ri)=gcd(ri1,0)=ri1gcd(a, b) = gcd(b, r_1) = ... = gcd(r_{i-1}, r_i) = gcd(r_{i-1}, 0) = r_{i-1}

となるが、 a,ba, b は互いに素なので gcd(a,b)=1gcd(a, b) = 1 。よって ri1=1r_{i-1} = 1 とわかるので、結局示すべき条件は

  • ax+by=1ax + by = 1 をみたす整数 x,yx, y が存在
  • x+0y=1\Leftrightarrow x + 0 \cdot y = 1 をみたす整数 x,yx, y が存在

となり、これは真であるから条件が示された。(証明終)

整数の基本的な性質

ここから整数の基本的な性質、及び素数の基本的な性質を取り上げますが、たいていの問題はこの 2 つのどちらかの議論に帰着させて考えることができると思います。てことで定石というか、これは信頼できる事実だとして覚えておくとよさそう。

💡
整数の基本的な性質

a,b,ca, b, c を整数として、 a,ba, b が互いに素であるとする。このとき、 acacbb の倍数であるならば、 ccbb の倍数である。

  • a,ba, b が互いに素
  • acacbb の倍数

のとき、

  • ccbb の倍数

といえます。

略証

a,ba, b は互いに素なので、 ax+by=1ax + by = 1 となる x,yx, y が存在する。このような x,yx, y について、上の等式の両辺を cc 倍すると acx+bcy=cacx + bcy = c となる。

acacbb の倍数だから、左辺 acx+bcyacx + bcybb の倍数。よって ccbb の倍数。 (証明終)

素数の基本的な性質

💡
素数の基本的な性質

pp を素数、a,ba, b を整数とする。このとき「 ababpp の倍数」ならば、「 aapp の倍数」または「 bbpp の倍数」が成立する。

これ、意外と意識しないとミスるんで気をつけてくださいね。pp が素数じゃないとだめです。3×43 \times 466 の倍数でも、334466 の倍数ではないですね。文字式になると本当にミスります。

略証

aapp の倍数ではないとき、 bbpp の倍数になることを示す。

aapp の倍数ではないので、 aapp は互いに素。よって ax+py=1ax + py = 1 なる整数 x,yx, y が存在し、このような x,yx, y について、両辺を bb 倍すると abx+pby=babx + pby = b となる。

ababpp の倍数であるから、左辺 abx+pbyabx + pbypp の倍数。よって bbpp の倍数になる。(証明終)


また、これを2素数でなく一般まで拡張して

💡
素数の基本的な性質(拡張版)

pp を素数、a1,a2,,ana_1, a_2, \ldots, a_n を整数とする。このとき「 a1a2ana_1 a_2 \cdots a_npp の倍数」ならば、「 a1a_1pp の倍数」または「 a2a_2pp の倍数」または…「 ana_npp の倍数」が成立する。

おわり。