COMP 2711 - Discrete Mathematical Tools for Computer Science

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\mid 12$ (3 divides 12)
• $3\nmid 11$ (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=\{0,1,\cdots ,m-1\}$$

Definition

For any $a,b\in {\mathbf{Z}}_m$:

$$\mathrm{\forall }a,b\in {\mathbf{Z}}_m$$$$a{+}_{m}b=(a+b)modm$$$$a{\cdot }_{m}b=(a\cdot b)modm$$

Properties

• Closure: $\mathrm{\forall }a,b\in {\mathbf{Z}}_m,a{+}_{m}b\in {\mathbf{Z}}_m,a{\cdot }_{m}b\in {\mathbf{Z}}_m$
• Associativity
  • $(a{+}_{m}b){+}_{m}c=a{+}_m(b{+}_{m}c)$
  • $(a{\cdot }_{m}b){\cdot }_{m}c=a{\cdot }_m(b{\cdot }_{m}c)$
• Commutativity:
  • $a{+}_{m}b=b{+}_{m}a$
  • $a{\cdot }_{m}b=b{\cdot }_{m}a$
• Distributivity
  • $a{\cdot }_m(b{+}_{m}c)=(a{\cdot }_{m}b){+}_m(a{\cdot }_{m}c)$
• Inverse: $\mathrm{\forall }a\in {\mathbf{Z}}_m,\mathrm{\exists }!b\in {\mathbf{Z}}_m,a{+}_{m}b=0,a{\cdot }_{m}b=1$

Congruences

If

$$a\equiv bmodm,c\in \mathbf{Z}$$

then:

$$a+c\equiv b+cmodm$$$$ac\equiv bcmodm$$

Greatest Common Divisor

The greatest common divisor is defined as:

$$gcd(a,b)=max(\{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\cdot 111+12$$$$111=9\cdot 12+3$$$$12=4\cdot 3$$$$gcd(123,111)=3$$

Step 2: Rewrite

$$12=123-1\cdot 111$$$$3=111-9\cdot 12$$

Step 3: Substitute

$$\begin{array}{rl}3& =111-9\cdot 12\\ & =111-9\cdot (123-1\cdot 11)\\ & =-9\cdot 123+10\cdot 111\end{array}$$

Multiplicative Inverses

For all $a\in {\mathbf{Z}}_m,m>1$ if $gcd(a,m)=1$, then:

$$\mathrm{\exists }!b,ab\equiv 1modm$$

Example: $a=4,m=9$

Step 1: Linear Combination

$$1=9-2\cdot 4$$

Step 2:

$$-2\equiv 7mod9$$

Linear Congruences

For $ax\equiv bmodm$ with $gcd(a,m)=1$:

$$a^{-1}ax\equiv a^{-1}bmodm$$

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

Chinese Remainder Theorem

For $x,y\in \{m_1,m_2,\cdots ,m_n\}$ such that $gcd(x,y)=1$:

$$\begin{array}{rl}x\equiv a_1& mod{m}_1\\ x\equiv a_2& mod{m}_2\\ ⋮\\ x\equiv a_n& mod{m}_n\end{array}$$

Let $m=m_1{m}_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_k{M}_k\equiv 1mod{m}_k$$

Finally, compute:

$$x=a_1{M}_1{y}_1+a_2{M}_2{y}_2+\cdots +a_n{M}_n{y}_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}modm$$

Repeated Squaring Method

Example: evaluate ${2048}^{13}mod2050$

$$\begin{array}{rl}{2048}^{2^0}mod2050& =2048\\ {2048}^{2^1}mod2050& =4\\ {2048}^{2^2}mod2050& =16\\ {2048}^{2^3}mod2050& =256\end{array}$$$$13=2^0+2^2+2^3$$$${2048}^{13}\equiv {2048}^{2^3}\cdot {2048}^{2^2}\cdot {2048}^{2^0}\equiv 2048\cdot 16\cdot 256\equiv 8mod2050$$

Fermat Little Theorem

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

$$a^{p-1}\equiv 1modp$$