整除関係の性質
整除関係の性質
\(a,b,c\)を任意の整数\(a,b,c\in\mathbb{Z}\)とする。
また、
\[ c\mid a_{1}\land c\mid a_{2}\land\cdots\land c\mid a_{n}\Rightarrow c\mid\sum_{k=1}^{n}a_{k} \] が成り立つ。
\[ c\mid a_{1}\land c\mid a_{2}\land\cdots\land c\mid a_{n}\Leftrightarrow\forall\left(x\right)_{j\in\left\{ 1,2,\cdots,n\right\} }\subseteq\mathbb{Z},c\mid\sum_{k=1}^{n}a_{k}x_{k} \] が成り立つ。
\[ a\mid b_{1}\land a\mid b_{2}\land\cdots\land a\mid b_{n}\Leftrightarrow a\mid\gcd\left(b_{1},b_{2},\cdots,b_{n}\right) \] が成り立つ。
また、
\[ a_{1}a_{2}\cdots a_{n}\mid c\Rightarrow a_{1}\mid c\land a_{2}\mid c\land\cdots\land a_{n}\mid c \] が成り立つ。
\[ pq\mid a\Leftrightarrow p\mid a\land q\mid a \] が成り立つ。
\[ a_{1}\mid a_{2}\land a_{2}\mid a_{3}\land\cdots\land a_{n-1}\mid a_{n}\Leftrightarrow\left|a_{1}\right|=\left|a_{2}\right|=\cdots=\left|a_{n}\right| \] が成り立つ。
また、
\[ a\mid b_{1}b_{2}\cdots b_{n}\land\bigwedge_{k=1}^{n}\gcd\left(a,b_{k}\right)\Rightarrow a\mid c \] が成り立つ。
\[ p\mid q\Leftrightarrow p=q \] が成り立つ。
\[ p\mid ab\Leftrightarrow p\mid a\lor p\mid b \] が成り立つ。
また、
\[ p\mid a_{1}a_{2}\cdots a_{n}\Leftrightarrow\bigvee_{k=1}^{n}p\mid a_{k} \] が成り立つ。
\(a,b,c\)を任意の整数\(a,b,c\in\mathbb{Z}\)とする。
(1)
\[ c\mid a\land c\mid b\Rightarrow c\mid\left(a+b\right) \] 逆は一般的に成り立たない。また、
\[ c\mid a_{1}\land c\mid a_{2}\land\cdots\land c\mid a_{n}\Rightarrow c\mid\sum_{k=1}^{n}a_{k} \] が成り立つ。
(2)
\[ a\mid b\Leftrightarrow\forall x\in\mathbb{Z},a\mid bx \](3)
\[ c\mid a\land c\mid b\Leftrightarrow\forall x,y\in\mathbb{Z},c\mid\left(ax+by\right) \] また、\[ c\mid a_{1}\land c\mid a_{2}\land\cdots\land c\mid a_{n}\Leftrightarrow\forall\left(x\right)_{j\in\left\{ 1,2,\cdots,n\right\} }\subseteq\mathbb{Z},c\mid\sum_{k=1}^{n}a_{k}x_{k} \] が成り立つ。
(4)
\[ a\mid b\land a\mid c\Leftrightarrow a\mid\gcd\left(b,c\right) \] また、\[ a\mid b_{1}\land a\mid b_{2}\land\cdots\land a\mid b_{n}\Leftrightarrow a\mid\gcd\left(b_{1},b_{2},\cdots,b_{n}\right) \] が成り立つ。
(5)
\[ ab\mid c\Rightarrow a\mid c\land b\mid c \] 逆は一般的に成り立たない。また、
\[ a_{1}a_{2}\cdots a_{n}\mid c\Rightarrow a_{1}\mid c\land a_{2}\mid c\land\cdots\land a_{n}\mid c \] が成り立つ。
(6)
\(p,q\)が互いに素な整数\(\gcd\left(p,q\right)=1\)とすると、\[ pq\mid a\Leftrightarrow p\mid a\land q\mid a \] が成り立つ。
(7)
\begin{align*} a\mid b & \Leftrightarrow-a\mid b\\ & \Leftrightarrow a\mid-b\\ & \Leftrightarrow\left|a\right|\mid\left|b\right| \end{align*}(8)
\[ a\mid b\land b\mid a\Leftrightarrow\left|a\right|=\left|b\right| \](9)
\[ a\mid b\land b\mid c\land c\mid a\Leftrightarrow\left|a\right|=\left|b\right|=\left|c\right| \] また、\[ a_{1}\mid a_{2}\land a_{2}\mid a_{3}\land\cdots\land a_{n-1}\mid a_{n}\Leftrightarrow\left|a_{1}\right|=\left|a_{2}\right|=\cdots=\left|a_{n}\right| \] が成り立つ。
(10)
\[ a\mid b\land b\mid c\Rightarrow a\mid c \] 逆は一般的に成り立たない。(11)
\[ a\mid b\Rightarrow ac\mid bc \] 逆は一般的に成り立たない。(12)
\[ a\mid bc\land\gcd\left(a,b\right)=1\Rightarrow a\mid c \] 逆は一般的に成り立たない。また、
\[ a\mid b_{1}b_{2}\cdots b_{n}\land\bigwedge_{k=1}^{n}\gcd\left(a,b_{k}\right)\Rightarrow a\mid c \] が成り立つ。
(13)
\(p,q\)が共に素数であるとき、\[ p\mid q\Leftrightarrow p=q \] が成り立つ。
(14)
\(p\)を素数とするとき、\[ p\mid ab\Leftrightarrow p\mid a\lor p\mid b \] が成り立つ。
また、
\[ p\mid a_{1}a_{2}\cdots a_{n}\Leftrightarrow\bigvee_{k=1}^{n}p\mid a_{k} \] が成り立つ。
(1)
\(\Rightarrow\)
\(c\mid a\land c\mid b\)のとき、ある整数\(m,n\in\mathbb{Z}\)が存在して\(a=mc\land b=nc\)となる。これより、\(\left(a+b\right)=\left(m+n\right)c\)となるので\(c\mid\left(a+b\right)\)となる。
\(\Leftarrow\)は一般的に成り立たない
反例で示す。\(a=b=1,c=2\)とすると、左辺は\(c\mid\left(a+b\right)\Leftrightarrow2\mid\left(1+1\right)\Leftrightarrow2\mid2\Leftrightarrow\top\)であるが、右辺は\(2\mid1\land2\mid1\Leftrightarrow\bot\land\bot\Leftrightarrow\bot\)となる。
従って逆は一般的に成り立たない。
(2)
\(\Rightarrow\)
\(a\mid b\)が成り立つときある整数\(n\in\mathbb{Z}\)が存在して\(b=na\)となる。この両辺に任意の整数\(x\in\mathbb{Z}\)を掛けると\(bx=xna\)となり、\(xn\)は整数なので\(a\mid bx\)となる。
\(\Leftarrow\)
任意の\(x\in\mathbb{Z}\)に対し、\(a\mid bx\)が成り立つので、\(x=1\)とすれば\(\top\Leftrightarrow a\mid bx\Leftrightarrow a\mid b\)となる。従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(3)
\(\Rightarrow\)
(1)(2)より、\(c\mid a\land c\mid b\rightarrow\forall x,y\in\mathbb{Z},c\mid ax\land c\mid by\rightarrow\forall x,y\in\mathbb{Z},c\mid\left(ax+by\right)\)となる。従って\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
条件より、任意の整数\(x,y\in\mathbb{Z}\)に対し、\(c\mid\left(ax+by\right)\)が成り立つので、\(x=1,y=0\)とすると、\(c\mid a\)が成り立ち、\(x=0,y=1\)とすると、\(c\mid b\)が成り立つ。これより、\(c\mid a\land c\mid b\)が成り立つ
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(4)
\(\Rightarrow\)
\(a\mid b\land a\mid c\)であるとき、ある整数\(m,n\in\mathbb{Z}\)が存在し、\(b=am,c=an\)となる。このとき、\(a\mid\gcd\left(b,c\right)\Leftrightarrow a\mid\gcd\left(am,bn\right)\Leftrightarrow a\mid a\gcd\left(m,n\right)\Leftrightarrow1\mid\gcd\left(m,n\right)\Leftrightarrow\top\)となる。
従って、\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
ある整数\(b',c'\in\mathbb{Z}\)が存在し、\(b=b'\gcd\left(b,c\right),c=c'\gcd\left(b,c\right)\)となる。また条件より、\(a\mid\gcd\left(b,c\right)\)であるので、ある整数\(n\in\mathbb{Z}\)が存在し、\(\gcd\left(b,c\right)=an\)となる。
これより、\(b=b'\gcd\left(b,c\right)=b'an,c=c'\gcd\left(b,c\right)=c'an\)となるので、\(a\mid b\Leftrightarrow a\mid b'an\Leftrightarrow1\mid b'n\Leftrightarrow\top\)となり、同様に\(a\mid c\Leftrightarrow\top\)となる。
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(5)
\(\Rightarrow\)
\(ab\mid c\)のとき、ある\(m\in\mathbb{Z}\)が存在し、\(c=abm\)となるので、\(c=a\left(bm\right)\)であるので\(a\mid c\)となる。同様に\(ab\mid c\)のとき、\(b\mid c\)となる。
従って、\(ab\mid c\)のとき、\(a\mid c\)かつ\(b\mid c\)となるので\(\Rightarrow\)が成り立つ。
逆は一般的に成り立たない。
反例で示す。\(a=b=c=2\)とすると右辺は\(a\mid c\land b\mid c\Leftrightarrow2\mid2\land2\mid2\Leftrightarrow\top\land\top\Leftrightarrow\top\)となり、左辺は\(ab\mid c\Leftrightarrow2\cdot2\mid2\Leftrightarrow4\mid2\Leftrightarrow2\mid1\Leftrightarrow\bot\)となる。
従って逆は一般的に成り立たない。
(6)
\(\Rightarrow\)
(5)より成り立つ。\(\Leftarrow\)
\(p\mid a\land q\mid a\)なのである整数\(m,n\in\mathbb{Z}\)が存在し、\(a=pm,a=qn\)となる。このとき、
\begin{align*} p\mid a\land q\mid a & \Rightarrow pq\mid aq\land pq\mid ap\\ & \Rightarrow\forall x,y\in\mathbb{Z},pq\mid\left(aqx+apy\right)\\ & \Leftrightarrow\forall x,y\in\mathbb{Z},pq\mid a\left(qx+py\right)\\ & \Rightarrow pq\mid a\gcd\left(p,q\right)\cmt{\because\exists x,y\in\mathbb{Z},\gcd\left(p,q\right)=qx+py}\\ & \Leftrightarrow pq\mid a\cmt{\because\gcd\left(p,q\right)=1} \end{align*} となる。
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(7)
\(a\mid b\)が成り立つとき、ある整数\(n\in\mathbb{Z}\)が存在して\(b=na\)となる。このとき、\(b=\left(-n\right)\left(-a\right)\)となるので、\(a\mid b\Rightarrow-a\mid b\)が成り立ち、\(a\rightarrow-a\)と置き換えれば、\(-a\mid b\Rightarrow-a\mid b\)となるので\(a\mid b\Leftrightarrow-a\mid b\)が成り立つ。
同様に\(-b=\left(-n\right)\)となるので、\(a\mid b\Rightarrow a\mid-b\)が成り立ち、\(b\rightarrow-b\)と置き換えれば、\(a\mid-b\Rightarrow a\mid b\)となるので\(a\mid b\Leftrightarrow a\mid-b\)が成り立つ。
次に\(a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)を示す。
\(a,b\in\mathbb{N}_{0}\)のとき、明らかに\(a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)が成り立つ。
\(a\in\mathbb{N},b\in\mathbb{N}^{-}\)のとき、\(-a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)となるので、\(a\mid b\Leftrightarrow-a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)となるので成り立つ。
\(a\in\mathbb{N}^{-},b\in\mathbb{N}\)のとき、\(-a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)となるので、\(a\mid b\Leftrightarrow-a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)となるので成り立つ。
\(a,b\in\mathbb{N}^{-}\)のとき、\(-a\mid-b\Leftrightarrow\left|a\right|\mid\left|b\right|\)となるので、\(a\mid b\Leftrightarrow-a\mid b\Leftrightarrow-a\mid-b\Leftrightarrow\left|a\right|\mid\left|b\right|\)となるので成り立つ。
これらより任意の整数\(a,b\)に対し\(a\mid b\Leftrightarrow\left|a\right|\mid\left|b\right|\)が成り立つ。
(8)
\(\Rightarrow\)
\(a\mid b\land b\mid a\)が成り立つときある整数\(m,n\in\mathbb{Z}\)が存在して\(b=ma,a=bn\)が成り立ち、\(a=mna\)となるもし\(a\ne0\)なら\(mn=1\)となるので、\(\left(m=1\land n=1\right)\lor\left(m=-1\land n=-1\right)\)となるが、\(a=b\lor a=-b\)となるので\(\left|a\right|=\left|b\right|\)となる。
もし\(a=0\)なら\(b=0\)となるので\(\left|a\right|=\left|b\right|\)が成り立つ。
従って\(a=0\)でも\(a\ne0\)でも\(\left|a\right|=\left|b\right|\)が成り立つ。
故に\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
\(\left|a\right|=\left|b\right|\)のとき、\(a=b\lor a=-b\)となる。\(a=b\)のとき、\(a\mid b\land b\mid a\Leftrightarrow a\mid a\land a\mid a\Leftrightarrow\top\)となり\(\Leftarrow\)が成り立つ。
\(a=-b\)のとき、\(a\mid b\land b\mid a\Leftrightarrow a\mid-a\land-a\mid a\Leftrightarrow\top\)となり\(\Leftarrow\)が成り立つ。
これより、\(a=b\)でも\(a=-b\)でも\(a\mid b\land b\mid a\Leftrightarrow\top\)が成り立つ。
従って\(\Leftarrow\)が成り立つ。
-
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(9)
\(\Rightarrow\)
\(a\ne0\land b\ne0\land c\ne0\)のとき、\begin{align*} a\mid b\land b\mid c\land c\mid a & \Rightarrow\left|a\right|\leq\left|b\right|\land\left|b\right|\leq\left|c\right|\land\left|c\right|\leq\left|a\right|\\ & \Leftrightarrow\left|a\right|\leq\left|b\right|\leq\left|c\right|\leq\left|a\right|\\ & \Leftrightarrow\left|a\right|=\left|b\right|=\left|c\right| \end{align*} \(a=0\lor b=0\lor c=0\)のとき、
\(a=0\)とすると、\(a\mid b\land b\mid c\land c\mid a\Leftrightarrow0\mid b\land b\mid c\land c\mid0\)となるが、これが真になるためには\(0\mid b\)が真にならなければいけなく\(b=0\)となる。
そして\(a=0\)\(\land b=0\)ならば\(a\mid b\land b\mid c\land c\mid a\Leftrightarrow0\mid0\land0\mid c\land c\mid0\)となり、これが真になるためには\(0\mid c\)が真にならなければいけなく\(c=0\)となる。
従って\(a=0\)とすると\(a=b=c=0\)とならなければいけない。
同様に\(b=0\)や\(c=0\)としても\(a=b=c=0\)とならなければいけない。
してがって\(a=0\lor b=0\lor c=0\)のとき、\(a=b=c=0\)なので、\(\left|a\right|=\left|b\right|=\left|c\right|\)が成り立つ。
これより、\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
\(\left|a\right|=\left|b\right|=\left|c\right|\)のとき、\(a\mid b\Leftrightarrow a\mid\pm a\Leftrightarrow\top\)同様に\(b\mid c\Leftrightarrow\top,c\mid a\Leftrightarrow\top\)となるので、\(a\mid b\land b\mid c\land c\mid a\Leftrightarrow\top\)となる。従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(10)
\(\Rightarrow\)
\(a\mid b\land b\mid c\)であるとき、ある整数\(m,n\in\mathbb{Z}\)が存在し、\(b=am,c=bn\)となるので、\(amn=bn=c\)となるので\(a\mid c\)となる。逆は一般的に成り立たない
反例で示す。\(1\mid1\)であるが、\(1\mid2\land2\mid1\Leftrightarrow\top\land\bot\Leftrightarrow\bot\)となる。
従って逆は一般的に成り立たない。
(11)
\(\Rightarrow\)
\(a\mid b\)であるとき、ある整数\(n\in\mathbb{Z}\)が存在し、\(b=an\)となり、両辺に\(c\ne0\)を掛けると、\(bc=acn\)となるので、\(ac\mid bc\)となる。逆は一般的に成り立たない。
\(c=0\)として\(a=2,b=1\)とすると、右辺は\(ac\mid bc\Leftrightarrow\left(2\cdot0\right)\mid\left(1\cdot0\right)\Leftrightarrow0\mid0\)\(\Leftrightarrow\top\)となるが左辺は\(a\mid b\Leftrightarrow2\mid1\Leftrightarrow\bot\)となる。従って逆は一般的に成り立たない。
\(c\ne0\)のときは\(\Leftarrow\)が成り立つ
\(c\ne0\)とすると、\(ac\mid bc\)であるとき、ある整数\(n\in\mathbb{Z}\)が存在し、\(bc=acn\)となり、両辺を\(c\ne0\)で割ると、\(b=an\)となるので、\(a\mid b\)となるので\(\Leftarrow\)が成り立つ。(12)
\(\Rightarrow\)
条件より、\(\gcd\left(a,b\right)=1\)なのである整数\(x,y\in\mathbb{Z}\)が存在し、\(ax+by=1\)となる。また、条件より\(a\mid bc\)なので、ある\(n\in\mathbb{Z}\)が存在し、\(bc=an\)となる。
これより、\(any=bcy=c\left(1-ax\right)=c-cax\)となり、\(c=any+cax=a\left(ny+cx\right)\)となるので、\(a\mid c\Leftrightarrow a\mid a\left(ny+cx\right)\Leftrightarrow1\mid\left(ny+cx\right)\Leftrightarrow\top\)となる。
従って題意は成り立つ。
逆は一般的に成り立たない
反例で示す。\(a=b=c=2\)とすると右辺は\(a\mid c\Leftrightarrow2\mid2\Leftrightarrow\top\)となり、左辺は\(a\mid bc\land\gcd\left(a,b\right)=1\Leftrightarrow2\mid2\cdot2\land\gcd\left(2,2\right)=1\Leftrightarrow2\mid4\land2=1\Leftrightarrow\bot\)となる。
従って逆は一般的に成り立たない。
(13)
\(\Rightarrow\)
条件より、\(p\mid q\)であるので、ある整数\(n\in\mathbb{Z}\)が存在し、\(q=pn\)となるが、\(q\)は素数なので\(n=\pm1\)となり、\(p\)も素数なので、\(n=1\)となる。従って、\(q=p\)となるので\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
\(p=q\)のとき明らかに\(p\mid q\)が成り立つ。\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。(14)
\(p\mid ab\)のとき、ある整数\(n\in\mathbb{Z}\)が存在し、\(ab=pn\)となる。\(p\nmid a\)とすると、\(p\)は素数なので\(\gcd\left(p,a\right)=1\)となるので、ある整数\(x,y\in\mathbb{Z}\)が存在し、\(px+ay=\gcd\left(p,a\right)=1\)となる。
これより、\(pny=aby=b\left(1-px\right)=b-bpx\)となるので、\(b=p\left(ny+bx\right)\)となるので、\(p\mid b\Leftrightarrow p\mid p\left(ny+bx\right)\Leftrightarrow1\mid\left(ny+bx\right)\Leftrightarrow\top\)となる。
同様に\(p\nmid b\)とすると、\(p\mid a\)が成り立つ。
従って、\(\top\Leftrightarrow\left(p\nmid a\rightarrow p\mid b\right)\land\left(p\nmid b\rightarrow p\mid a\right)\Leftrightarrow\left(p\mid a\lor p\mid b\right)\land\left(p\mid b\lor p\mid a\right)\Leftrightarrow p\mid a\lor p\mid b\)となるので\(\Rightarrow\)が成り立つ。
\(\Leftarrow\)
\(p\mid a\)のとき、ある整数\(n\in\mathbb{Z}\)が存在し、\(a=pn\)となる。両辺に\(b\)を掛けると、\(ab=p\left(nb\right)\)となるので、\(p\mid ab\)となる。
同様に\(p\mid b\)のときも\(p\mid ab\)となる。
従って\(\Leftarrow\)が成り立つ。
\(\Leftrightarrow\)
これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。ページ情報
| タイトル | 整除関係の性質 |
| URL | https://www.nomuramath.com/jmyjq9er/ |
| SNSボタン |
整徐関係の定義
\[
\exists n\in\mathbb{Z},a=bn\rightarrow b\mid a
\]
整除関係の基本的な値
\[
\forall a\in\mathbb{Z},\pm1\mid a
\]
整徐関係と半順序関係
整除関係と大小関係
\[
\forall a,b\in\mathbb{N},a\mid b\rightarrow a\leq b
\]