MATH

ガウス　"数学は科学の女王であり，数論は数学の女王である”

〇数について

自然数：正の整数 \((1,2,\cdots)\)

倍数：\(c=a\times b\)の時,\(c\)は\(a,b\)の倍数という．

〇素因数分解

\(a^{m}\times b^{n}\)の正の約数の個数は，\((m+1)(n+1)\)

正の約数の総和は，\((1+a+\cdots+a^{m})(1+b+\cdots+b^{n})\)

例：\(18=2^{1}\times3^{2}\)

正の約数の個数については，2を0～1個，3を0～2個選ぶので，\((1+1)(2+1)=9\)

正の約数の総和については，2からは1,2，3からは\(1,3,3^{2}\)を選んで足し合わせるので，\((1+2)(1+3+3^{2})=39\)

〇最大公約数，最小公倍数

\(a=a'g,~b=b'g\) (\(a',b'\)は互いに素)と表すことができる．

\(l=a'b'g\)なので，\(ab=lg\)が成り立つ．

性質：

連続する二つの整数は互いに素 \((n,n+1)\)

〇倍数の性質

2の倍数は，下一桁が偶数．（9992）

3の倍数は，全ての桁の数字を足した数が3の倍数．（54321）

5の倍数は，下一桁が5 or 0

10の倍数は，下一桁が0

他の倍数の判定方法も以下のようになるが，あまり使わないと思う．

4の倍数は，下二桁が4の倍数

8の倍数は，下三桁が8の倍数

9の倍数は，全ての桁の数字を足した数が9の倍数．

〇連続する整数の積の性質

連続する\(n\)個の整数の積は\(n!\)の倍数である．

○整数の除法

\(a\)は整数，\(b\)は正の整数，\(m\)は商(整数)，\(r\)は余り\((0\leqq r \leqq b-1)\)とすると，\(a=bm+r\)と示せる．

〇余りを用いた整数の表し方

〇合同式

余りの表し方として\(a,b\)を\(m\)で割ったときの余りが等しいとき，\(a \equiv b\) \((\mod m)\)と表す．

合同式は足し算(\(a+c\equiv b+d\))，引き算(\(a-c\equiv b-d\))，掛け算(\(ac\equiv bd\))は成立する．

○ユークリッドの互除法

\(a,b\)は自然数\((a>b)\),\(m\)は商(整数)，\(r\)は余り\((0\leqq r \leqq b-1)\)とするとき，\(a\)と\(b\)の最大公約数と\(b\)と\(r\)の最大公約数は等しい．

この性質を利用すると，大きい数でも簡単に最大公約数を求めることができる．

例：642と564の最大公約数は6である．ユークリッドの互除法で割り切った時の\(b\)の値である．

642=546×1+96

546=96×5+66

96=66×1+30

66=30×2+6

30=6×5

642と564の最大公約数＝546と96の最大公約数＝…＝30と6の最大公約数

〇不定方程式の整数解

\(ax+by=c\)の場合，

\(a,b\)の最大公約数\(g\)が存在するとき，\(a=a'g,~b=b'g\) (\(a',b'\)は互いに素)として，

\(\displaystyle a'x+b'y=\frac{c}{g}\),　\(\displaystyle \frac{c}{g}\)が整数でない場合は解なし．

\(\displaystyle \frac{c}{g}=c'\)が整数の場合，\(a'(x-p)=-b'(y-q)\)で表せる\(p,q\)を見つけ（※），\(a',b'\)は互いに素なので，\(x-p=-b'k,~y-q=a'k\)が解となる．

他に因数分解ができる場合（例：\((x+a)(y+b)=c\)はx+a,y+bはcの約数であることを利用）や二次方程式系なら判別式\(D\)で範囲を絞る方法がある．