Discrete Math Quick Notes

This is the review notes for key concepts and theorems in discrete mathematics, particularly focusing on modular arithmetic, divisibility, and the properties of integers.

Modular Notation

Divisibility Notation

\(3\mid12\) (3 divides 12)
\(3\nmid11\) (3 does not divide 11)

Euclid’s Division Theorem

For integers \(a\) and \(d\):

\[ a=dq+r \]

Note	Name	Note	Name	Note	Name	Note	Name
\(d\)	divisor	\(a\)	dividend	\(q\)	quotient	\(r\)	remainder

Quotient Ring

The set of integers modulo \(m\) is defined as:

\[ {\mathbf Z}_m=\set{0,1,\cdots,m-1} \]

Definition

For any \(a,b\in\mathbf Z_m\):

\[ \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

The greatest common divisor is defined as:

\[ \gcd(a,b)=\max(\set{d\in{\mathbf Z} |\ d\mid a, d\mid b}) \]

Euclidean Algorithm

The process is as follows:

\[ a=bq+r \]

Then:

\[ \gcd(a,b)=\gcd(b,r) \]

Bézout’s Theorem

For all \(a,b\in\mathbf Z^+\), there exist integers \(s\) and \(t\) such that:

\[ \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

For all \(a\in\mathbf Z_m,m>1\) if \(\gcd(a,m)=1\), then:

\[ \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

For \(ax\equiv b\bmod m\) with \(\gcd(a,m)=1\):

\[ a^{-1}ax\equiv a^{-1}b\bmod m \]

If \(\gcd(a,m)\neq1\), there may be multiple solutions or no solution.

Chinese Remainder Theorem

For \(x,y\in\set{m_1,m_2,\cdots,m_n}\) such that \(\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} \]

Let \(m=m_1m_2\cdots m_n\) and define:

\[ M_k=\frac m{m_k}, k=1,2,\dots,n \]

If \(\gcd(m_k,M_k)=1\), then:

\[y_kM_k\equiv1\bmod m_k\]

Finally, compute:

\[ 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

For any prime \(p\) and integer \(a\) such that \(p\nmid a\):

\[ a^{p-1}\equiv1\bmod p \]