剰余と合同式

SNS Accounts

SHARE

Side Menu

高校数学編

論理・集合

数・式

変化

空間

確率

論理・集合

数・式

群環体論

線形代数学

整数論

表現論

実解析学

複素解析学

関数解析学

位相幾何学

微分幾何学

代数幾何学

Side Menu

数・式

有理式

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\)
     (二項定理)

例題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

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

←約数と倍数


Menu

ユークリッドの互除法→