Discrete Math Quick Notes
Number Theory
Modular Notation
==Divisibility Notation==
\[
3\mid12,\ \ 3\nmid7
\]
Euclid’s Division Theorem
\[
a=dq+r
\]
| Note | Name |
|---|---|
| \(d\) | divisor |
| \(a\) | dividend |
| \(q\) | quotient |
| \(r\) | remainder |
Quotient Ring
\[
{\mathbf Z}_m=\set{0,1,\cdots,m-1}
\]
==Definition==
\[
\forall a,b\in{\mathbf Z}_m
\]
\[
a+_mb=(a+b)\bmod{m}
\]
\[
a\cdot_mb=(a\cdot b)\bmod m
\]
Properties
- Closure: \(\forall a,b\in{\mathbf Z}_m, a+_mb\in{\mathbf Z}_m,a\cdot_mb\in{\mathbf Z}_m\)
- Associativity
- \((a+_mb)+_mc=a+_m(b+_mc)\)
- \((a\cdot_mb)\cdot_mc=a\cdot_m(b\cdot_mc)\)
- Commutativity:
- \(a+_mb=b+_ma\)
- \(a\cdot_mb=b\cdot_ma\)
- Distributivity
- \(a\cdot_m(b+_mc)=(a\cdot_mb)+_m(a\cdot_mc)\)
- Inverse: \(\forall a\in{\mathbf Z}_m,\exists!b\in{\mathbf Z}_m,a+_mb=0,a\cdot_mb=1\)
Congruences
If
\[
a\equiv b\bmod m, c\in \bf Z
\]
Then
\[
a+c\equiv b+c\bmod m
\]
\[
ac\equiv bc\bmod m
\]
Greatest Common Divisor
\[
\gcd(a,b)=\max(\set{d\in{\mathbf Z} |\ d\mid a, d\mid b})
\]
Euclidean Algorithm
\[
a=bq+r
\]
\[
\gcd(a,b)=\gcd(b,r)
\]
Bézout’s Theorem
\[
\forall a,b\in{\mathbf Z}^+, \exists s,t\in \bf Z
\]
\[
\gcd(a,b)=sa+tb
\]
==Extended Euclidean Algorithm==
Example: express \(\gcd(123,111)\) as a linear combination of \(123\) and \(111\)
Step 1: find
gcd()\[123=1\cdot111+12\]\[111=9\cdot12+3\]\[12=4\cdot3\]\[\gcd(123,111)=3\]Step 2: Rewrite
\[12=123-1\cdot111\]\[3=111-9\cdot12\]Step 3: Substitute
\[\begin{aligned}3&=111-9\cdot12\\&=111-9\cdot(123-1\cdot11)\\&=-9\cdot123+10\cdot111\end{aligned}\]
==Multiplicative Inverses==
\[
\forall a\in{\mathbf Z}_m,m>1,\gcd(a,m)=1
\]
\[
\exists! b,ab\equiv1\bmod m
\]
Example: \(a=4,m=9\)
Step 1: Linear Combination
\[1=9-2\cdot4\]Step 2:
\[-2\equiv7\bmod9\]
Linear Congruences
\[
ax\equiv b\bmod m, \gcd(a,m)=1,x=?
\]
\[
a^{-1}ax\equiv a^{-1}b\bmod m
\]
If \(\gcd(a,m)\neq1\), multi solutions or no solution
Chinese Remainder Theorem
\[
\forall x,y\in\set{m_1,m_2,\cdots,m_n}, \gcd(x,y)=1
\]
\[
\begin{aligned}
x\equiv a_1&\bmod m_1 \\
x\equiv a_2&\bmod m_2 \\
\vdots \\
x\equiv a_n&\bmod m_n
\end{aligned}
\]
\[
m=m_1m_2\cdots m_n
\]
\[
M_k=\frac m{m_k}, k=1,2,\dots,n
\]
\[
\forall\gcd(m_k,M_k)=1,\ y_kM_k\equiv1\bmod m_k
\]
\[
x=a_1M_1y_1+a_2M_2y_2+\cdots+a_nM_ny_n
\]
\[
x\equiv a_1\cdot m_1\cdot m_1^{-1}+a_2\cdot m_2\cdot m_2^{-1}+\cdots+a_n\cdot m_n\cdot m_n^{-1} \bmod m
\]
Repeated Squaring Method
Example: evaluate \(2048^{13}\bmod2050\)
\[\begin{aligned}2048^{2^0}\bmod2050&=2048\\2048^{2^1}\bmod2050&=4\\2048^{2^2}\bmod2050&=16\\2048^{2^3}\bmod2050&=256\\\end{aligned}\]\[13=2^0+2^2+2^3\]\[2048^{13}\equiv2048^{2^3}\cdot2048^{2^2}\cdot2048^{2^0}\equiv2048\cdot16\cdot256\equiv8\bmod2050\]
==Fermat Little Theorem==
\[
\forall p\in{\mathbf P},p\nmid a
\]
\[
a^{p-1}\equiv1\bmod p
\]