剰余と合同式

6.除法の性質

除法の定理

整数\(a\),正整数\(b\)に対して
\(a=bq+r\)     \(0≤r<b\)
を満たす整数\(q,r\)がただ1組定まる

証明
存在性

実数全体を\(...,[-2b,-b),[-b,0),[0,b),[b,2b),...\)
と分解する

\(qb≦a<(q+1)b\)
を満たす整数\(q\)は明らかに存在する

両辺に\(-qb\)を加えると
\(0≦a-qb<b\)
整数の性質から\(a-bq\)は整数であり、\(r\)とする
\(a=qb+r(0≦r<b)\)となる

\(q,r\)の存在性が示された


一意性

\(q,r\)が二通りで表されると仮定する
①\(a=bq+r\)
②\(a=bq'+r'\)

②-①     \(b(q'-q)=(r-r')\)

\(r-r'\)は\(b\)の倍数になるが\(|r-r'|<b\)なので\(r-r'=0\)となり、式から\(q'-q=0\)
\(r=r' ,q=q'\)

\(q、r\)の一意性が示された


POINT

この定理は多くの定理の根拠となる非常に大事な性質である
剰余\(r\)が1通りに表せることから整数を剰余で分類できる

7.合同式

合同式

\(m|a-b\)\( \Leftrightarrow a≡b\) \( (mod\) \(m)\)
\(m\)を法として合同という

言い換え

\(a\)と\(b\)の\(m\)で割った余りが等しいことを意味する

\(10≡7≡4≡1≡-2\) \((mod\) \(3)\)

性質

\(a≡b,c≡d\) \((mod\,m)\)のとき

  • \(a+c≡b+d\)
  • \(a-c≡b-d\)
  • \(ac≡bd\)
  • \(a^n≡b^n\)     \((n \in \mathbb{N})\)
証明

合同式は\(mod\,m\)とする
左辺、右辺共に下記と合同になる

  • \(a+c=mq+r+mq'+r'\\=m(q+q')+(r+r')≡\bf r+r'\)
  • \(a-c=mq+r-(mq'+r')\\=m(q-q')+(r-r')≡\bf r-r'\)
  • \(ac=(mq+r)(mq'+r')=\\m(mqq'+qr'+q'r)+(rr')≡\bf rr'\)
  • \(a^{n}=(mq+r)^n=m(...)+r^n≡\bf r^n\)
         (二項定理)

性質

\(a≡b,c≡d\) \((mod\,m)\)のとき

  • \(a+c≡b+d\)
  • \(a-c≡b-d\)
  • \(ac≡bd\)
  • \(a^n≡b^n\)     \((n \in \mathbb{N})\)
証明

合同式は\(mod\,m\)とする
左辺、右辺共に下記と合同になる

  • \(a+c=mq+r+mq'+r'\\=m(q+q')+(r+r')≡\bf r+r'\)
  • \(a-c=mq+r-(mq'+r')\\=m(q-q')+(r-r')≡\bf r-r'\)
  • \(ac=(mq+r)(mq'+r')=\\m(mqq'+qr'+q'r)+(rr')≡\bf rr'\)
  • \(a^{n}=(mq+r)^n=m(...)+r^n≡\bf r^n\)
         (二項定理)

例題1

\(19^{2014}\)を\(24\)で割った余りを求めよ

解説

\(19^{2014}=(19^2)^{1007}=361^{1007}≡1^{1007}=1 (mod\,24)\)
4番目の性質を使った


例題2

\(n\)が整数ならば\(a^2\)の余りは\(0\)または\(1\)

解説

\(n≡0,n≡1,n≡2\)のいずれかであるので全て確かめる

\(a≡0\Rightarrow a^2≡0^2=0\,(mod\,3) \,\,\,\,\,\,\,\,\,\)
\(a≡1\Rightarrow a^2≡1^2=1\,(mod\,3)\,\,\,\,\,\,\,\,\,\)
\(a≡2\Rightarrow a^2≡2^2=4≡1\,(mod\,3)\)

よって\(a\)が整数\(\Rightarrow\) \(a^2≡0\) または \(a^2≡1\)


POINT

このように剰余で分類することで無限個ある整数を\(\bf m\)個の合同な組みにまとめられるので整数の証明に使える

例題3

\(3\)の倍数の整数の各位の数の和は\(3\)の倍数

解説

\(3\)の倍数の整数\(x\)の各位の数を1の位から順に\(a_0,a_1...a_n\)とすると
\(x=10^na_n+10^{n-1}a_{n-1}...+a_0\\≡1^na_n+1^{n-1}a_{n-1}...+a_0\\ \bf =a_n+a_{n-1}...+a_0\\≡0\)


POINT

他の倍数の判定法も同じように示せる