8.22 Divisibility
1.Divisibility
\(a,b\in\Z,a\neq 0\). We say that "\(a\) divides \(b\)" or "\(a\) is a divisor of \(b\)", if \(\exists k\in \Z|a\times k=b\).
We write \(a\mid b\)
In case there is no \(k\in\Z|a\times k=b\), we write \(a\nmid b\)
Note that \(\forall a\in\Z\), \(a|0\) since \(a\times 0=0\)
Notation
\(a\in\Z\), \(Div(a)=\{b\in\Z:b\mid a\}\) \(Div_{+}(a)=\{b\in\N:b\mid a\}\)
Proposition
If \(a,b\in\Z\), \(a\mid b\) then \(Div(a)\subseteq Div(b)\)
Take \(c\in Div(a)\). Then \(\exists k\in\Z:c\times k=a\),
Since \(a\in Div(b),b=a\times h, h\in \Z\)
So \(b=a\times h=c\times k\times h\Rightarrow c\in Div(b)\)
Remark
\(\left(\N,R\right)~nRm\Leftrightarrow n\mid m\)
This is a partially ordered set
- \(aRa~~\forall a\in \N:a\mid a~~~\forall a\in \N\)
- \(aRb\wedge~bRa:a\mid b\wedge b\mid a\Rightarrow a\leq b\wedge b\leq a\Rightarrow a=b\)
- \(aRb\wedge ~bRc\Rightarrow~aRc:a\mid b\wedge b\mid c\Rightarrow a\mid c\) (Look the previous board)
Not a total order: \(2\nmid3\wedge 3\nmid2:~2\cancel{ R}3\wedge3\cancel{ R}2\)
Question Is\((\Z,\mid )\) a poset?(Note: poset means "partially ordered set")
No, the Antisymmetry is not satisfied.
Antisymmetry Issue: Consider \(a = 1\) and \(b = -1\).* \(1 \mid (-1)\) because \(-1 = 1 \times (-1)\).
- \(-1 \mid 1\) because \(1 = (-1) \times (-1)\).
- However, \(1 \neq -1\).
Properties
\(a,b,d\in\Z\), \(d\mid a\wedge d\mid b\Rightarrow d\mid m\times a+n\times b\), \(\forall n,m \in\Z\)
Proof
\(a=d\cdot k,b=d\cdot h~~~~(~k,h\in\Z.)\)
\(m\cdot a+mb=m\cdot d\cdot k+m\cdot d\cdot h=d\cdot\left(m\cdot k+mh\right)\Rightarrow d\mid m\cdot a+m\cdot b~(\forall m,n\in\mathbb{Z})\)
2.Integer division
\(m,d\in \Z,d\neq0.\)
Then there exists \(q,r\in\Z\) such that
\(m=d\cdot q+r~~~with~~~0\leq r<\left|d\right|\)
\(d\) is divisor \(q\) is quotient \(r\) is reminder
Then we can get the theorem (The \(q\) and \(r\) are unique)
Examples
\(m=7,d=2:~~~7=2\times3+1\)
\(m=-13,d=3~~~~~-13=3\times(-5)+2\)
\(m=11,d=-2~~~~11=\left(-2\right)\times\left(-5\right)+1\)
The proof
First, uniqueness
Suppose \(m>0,d>0\) and
\(m=d\times q+r\) and also \(m=d\times q\prime+r\prime\) \(0\leq r<d\), \(0\leq r\prime<d\)
(Two different integer divisions)
Note that: if \(q=q\prime\Rightarrow r=r\prime\)
Since \(d\times q+r=d\times q\prime+r\prime\)
Suppose \(q\neq q\prime\) then \(q>q\prime\) or \(q<q\prime\)
Suppose \(q<q\prime\) Write
\(r=m-dq=m-dq\prime+dq\prime-dq=r\prime+d(q\prime-q)\geq r\prime+d\geq d\)
Contradiction! Then \(q=q\prime\)
We have proved uniqueness.
Now the existence: \(m>0,d>0\)
Consider the set \(A=\{x\in\N:m=d\times q+x~for~some~q\in\Z\}\)
Note that \(A\neq \emptyset\), since \(m=d\times 0+m\Rightarrow m\in A\)
By W.O.P. A has a first element: \(r=min(A)\)
Since \(r\in A\), we have \(m=d\times q+r\) ,\(r\geq 0\)
We still need to prove that \(0\leq r<d\)
Suppose not : \(r\geq d\)
\(m=dq+r=d(q+1)+r-d\Rightarrow r-d\in A,r-d<r\)
Contradiction
So, \(0\leq r<d\)
Application: Writing numbers in different bases
Observe that: \(137=1\times 10^2+3\times 10^1+7\times 10^0\)
\(13=1\times 10^1+3\times 10^0\)
and also \(13=8+4+1=1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0\)
\(13=(1101)_2\)
Also \(13=9+3+1=1\times 3^2+1\times 3^1+1\times 3^0\)
\(13=(111)_3\)
\(16=2^{4}=(10000)_{2}\)
\(16=9+6+1=9+2\times3+1=1\times3^{2}+2\times 3^{1}+1\times3^{0}\\16=\left(121\right)_{3}\)
Positional notation of a number \(m\) in base \(b\):
Given \(m\in\N,b\in\N\) find the digits of \(m\) in base \(b\)
\(m=d_{k}b^{k}+d_{k-1}b^{k-1}+\cdots+d_{1}b^{1}+d_{0}\cdot b^0\)
\(m=\left(d_{k}d_{k-1}d_{k-2}\cdots d_{1}d_{0}\right)_b\)
\(d_{j}\in\{0,1,2,\cdots,b-1\}\)
Example: \(m=137, b=3\)
By the division algorithm
Now
\(137=(12002)_{3}\)
In general, for \(m\in\N,b\in\N\)
\(r_{0}r_{1}\cdots r_{k}q_k\) are digits
3.\(Div\left(a,b\right)\)
\(a,b\in\Z\), \(Div\left(a,b\right)=\{d\in\mathbb{Z}:d\mid a\wedge d\mid b\}\neq\emptyset\), \(Div_{+}\left(a,b\right)=\{d\in\mathbb{N}:d\mid a\wedge d\mid b\}\neq\emptyset\)
Common divisors
4.Greatest common divisor
\(g.c.d.(a,b),~~~(a,b\in\Z)\)
The \(g.c.d.(a,b)\) is a number \(d\) defined by the two properties
-
\(d\mid a\wedge d\mid b\)
-
Any other common divisor \(c\in Div(a,b)\) satisfies \(c|d\)
Notation
we also write \(g.c.d.(a,b)=(a:b)\)
Proposition
\((a:b)=max(Div(a,b))\)
Example
\(Div_{+}(18)=\{1,2,3,\textcircled{6},9,18\}\)
\(Div_{+}\left(12\right)=\left\{1,2,3,4,\textcircled{6},12\right\}\)
\((18:12)=6\)
Proof of the proposition
Let \(d=(a:b)\) we need to prove that \(d\geq c\) for any \(c\in Div(a,b)\)
Let \(c\in Div(a,b)\Rightarrow c\mid d\Rightarrow c\leq d\)
5.Theorem of Euclidean Algorithm
Let \(a,b\in\Z\) then
\(g.c.d.(a,b)=g.c.d.(b,r)\) where \(r\) is the reminder in the division of \(a\) by \(b\): \(a=b\times q+r\)
Proof
Put \(d=g.c.d.(a,b), d\prime=g.c.d.(b,r)\)
First, note that \(d|a\wedge d|b\) then \(d|m\times a+n\times b\) for any choice of \(n,m\in\Z\) (For example \(m=1,n=-q\))
\(\Rightarrow d|a-qb\Rightarrow d|r\Rightarrow d|d\prime\)
Now, \(d^{\prime}|b\wedge d^{\prime}|r.~~then~d^{\prime}|m\cdot b+n\cdot r~~\forall m,n\in \Z.\)
\(\left(m=q,n=1\right)\Rightarrow d^{\prime}\mid b\cdot q+r\Rightarrow d^{\prime}\mid a\Rightarrow d^{\prime}\mid d\)
Example
\((210:165)=(165:45)=(45:30)=(30:15)=(15:0)=15\)
Last non-zero reminder
\((125:27)=(27:17)=(17:10)=(10:7)=(7:3)=(3:1)=(1:0)=1\)
The process of Euclidean algorithm is
\(\begin{aligned}&a=b\cdot q_{1}+r_1\\&b=r_{1}\cdot q_{2}+r_2\\&r_{1}=r_{2}\cdot q_{3}+r_3\\&r_{2}=r_3\cdot q_{4}+r_4\\&r_{k-3}=r_{k-2}\cdot q_{k-1}+r_{k-1}\\&r_{k-2}=r_{k-1}\cdot q_{k}+0(r_k)\end{aligned}\)
Last non-zero reminder
\(r_{k-1}=\left(a:b\right)\)
Remark
By the Euclidean algorithm we have that \(gcd(a,b)=gcd(b,r_1)=......=gcd(r_{k-1},0)=r_{k-1}\)
Note:
\(125=27.4+17\\27=17.1+10\\17=10.1+7\\10=7.1+3\\7=3.2+1\\1=g.c.d\left(125,27\right)\)
6.Bézout's Theorem 裴蜀定理
\(a,b\in\Z,\exists m,n\in\Z\)
\((a:b)=am+bn\)
(Consider \(a,b\in\N,b\leq a\))
If \(b\mid a\Rightarrow(a:b)=b=0\times a+1\times b\)
Let \(r_k\) be the reminder obtained in the \(k^{th}\) step in the algorithm
We will prove that \(\exists {m_{k},n_{k}\in\mathbb{Z}}~|~r_{k}=m_{k}\cdot a+n_{k}\cdot b.~~~\forall k\in\N\)
Induction in \(k\) (Strong version)
We need to prove: (1)\(r_{1}=m_{1}a+n_{1}b\)
(2) It true for all \(r_j\) \(1\leq j\leq k-1\Rightarrow~True~for~r_k\)
-
We know that \(a=b\cdot q_{1}+r_{1}\Rightarrow r_{1}=1\cdot a+\left(-q_1\right)\cdot b\)
Now for \(r_k\): \(r_{k-2}=r_{k-1}\cdot q_{k}+r_{k}\)
by hypothesis:
\[ r_{k-1}=m_{k-1}\cdot a+n_{k-1}\cdot b\\r_{k-2}=m_{k-2}\cdot a+n_{k-2}\cdot b \]
Then
7.Consequences
-
\(a\mid bc\wedge\left(a:b\right)=1\Rightarrow a\mid c\)
write \(1=m\cdot a+n\cdot b\)
multiply by \(c\):
\[ c=m\cdot a\cdot c+n\cdot b\cdot c\\c=m\cdot a\cdot c+n\cdot a\cdot k\\c=a\cdot\left(m\cdot c+n\cdot k\right) \]Remark: The result can be false if \(gcd(a,b)\neq 1\).
For example, \(6\mid2\cdot3\) and \(gcd(6,2)=2\neq 1\) but \(6\nmid 3\)
-
\(\left(a:b\right)=1,a\mid c\wedge b\mid c\Rightarrow a\cdot b\mid c\)
Again
\[ 1=m\cdot a+n\cdot b \\c=m\cdot a\cdot c+n\cdot b\cdot c \\c=m\cdot a\cdot b\cdot k+n\cdot b\cdot a\cdot h\\c=a\cdot b\left(m\cdot k+n\cdot h\right)\Rightarrow ab\mid c \]
8.Prime numbers
\(P=\left\{m\in N,m>1:Div_{+}\left(m\right)=\left\{1,m\right\}\right\}\)
Properties
-
p prime, \(b\in\Z,p\nmid b\Rightarrow(p:b)=1\)
-
p prime, \(p\mid a\cdot b\Rightarrow p\mid a~or~p\mid b\)
If \(p\nmid b\Rightarrow\left(p:b\right)=1\Rightarrow p\mid a\)