Discrete Maths

Dividability

Def:

If there exists $k \in \mathbb{Z}$, such that $b = ak$ for $a, b \in \mathbb{Z}$, we write $a \mid b$ (read as "$a$ divides $b$").

If no such $k$ exists, we write $a \nmid b$ ($a$ does not divide $b$)

Ex: $5 \mid 25$, but $5 \nmid 26$

If $a \mid b$, then $k$ is the quotient

If $a \nmid b$, there exists $r$ and $q$ in the integers, such that $b = aq + r$, where $r$ is the remainder.

Note: $a \mid b \neq \frac{b}{a}$

Mathematical version: $$a \mid b \Leftrightarrow \exists k \in \mathbb{Z}: b = ak$$

Examples

$a \mid 0$ -> True $0 \mid 0$ -> True $0 \mid b$ -> True if $b = 0$

Theory

For $a, b, m, n, c \in \mathbb{Z}$, if $c \mid a$ and $c \mid b$, then $c \mid (ma + nb)$

Factors

How many factors does $144$ have?

There are a few ways to find out:

• Work through each numbers (very slow)
• Find the prime factors and combine all possibilities of each
• Example below:

Prime Factorisation of $144$: $2^4 * 3^2$
We can combine them such that we get all of the factors:

• $2^0 * 3^0 = 1$
• $2^1 * 3^0 = 2$
• ...
• $2^4 * 3^0 = 16$
• $2^0 * 3^1 = 3$
• $2^1 * 3^1 = 6$
• ...
• $2^4 * 3^2 = 144$

Using this method, we can count the number of factors and we'll get the product of one more than each exponent in the prime factorisation.
Since $144 = 2^4 * 3^2$, the number of factors is $5 * 3 = 15$.

Example

Find the number of factors for $(1024)(144)(10 000 000)$

We must first break it down into the prime factorisation. We can either multiply them together first and have a large and complex number, or we can get the factorisations first and make it much easier:

$1024 = 2^{10}$
$144 = 2^3 3^2$
$10 000 000 = 5^7 2^7$ $(1024)(144)(10 000 000) = (2^{10})(2^3 3^2)(5^7 2^7) = 2^{21} 5^7 3^2$

Now that we have the prime factorisation, we can add one to each exponent and find the product to get the number of factors:

$22 * 8 * 3 = 528$

Thus, $(1024)(144)(10 000 000)$ has $528$ factors.

Prime Numbers

An integer $p > 1$ is called prime if it is not divisible by an integer $\pm 1$ or $\pm p$, otherwise it is called composite

Note: $1$ is considered neither prime nor composite

Is $4321$ prime?

We need to check all potential factors. To do this, we must check only up to $$\left \lfloor \sqrt{4321} \right \rfloor = 65$$

Now we can check each number.

| Check | If the number we check is not a multiple, then neither are... | | $2$ | $4, 6, 8, \dots , 64$ | | $3$ | $9, 15, 21, \dots $ | | $4$ | This was covered by $2$ | | $5$ | $25, 35, 45, \dots $ | | $\dots$ | | | $29$ | $29 \mid 4321$, so it is not prime. |

The Fundamental Theorem of Arithmetic

For every positive integer $n \ge 2$, $n$ can be written as a product of one or more primes

Note: This is also known as prime factorisation

Proof by Strong Induction

BC: let $n = 2$ $2$ is prime, thus, $P(2)$ holds.

IH: Assume $P(k)$ holds for integer $k = 3, 4, 5, \dots, n$

IS: Consider $n + 1$. There are two cases:

1. $n + 1$ is prime, thus we are done.
2. $n + 1$ is composite, then $n + 1 = ab$ for some positive integers $a, b$ such that $a < n + 1$ and $b < n + 1$. By IH, both $a$ and $b$ can be written as a product of primes. Thus $ab$ is a product of primes.

Theorem: There are infinitely many primes

Proof

Suppose for a contradiction that there are finitely many primes.
List them: $P_1, P_2, P_3, \dots, P_n$ $n \in \mathbb{Z}^+$

let q = $P_1*P_2*P_3*\dots*P_n + 1$ $$\prod_{i=1}^n (P_i) + 1$$

$P_i \nmid q$ for any $i = 1, 2, \dots, n$

Thus, $q$ is prime, but $q = P_i$ for $i = 1, 2, \dots, n$ therefore, $q$ is not in the list of all primes, a contradiction. Thus, there are infinitely many primes.

Proofs by Contradictions

1. Argue the hypothesis holds
2. Negate the conclusion
3. Break Maths

Example

Prove that $\sqrt{2}$ is irrational

Proof:

AFAC (Assume for a contradiction) that $\sqrt{2}$ is rational. Then, for some $a, b \in \mathbb{Z}$, $\sqrt{2} = \frac{a}{b}$ such that $a$ and $b$ have no common factors(This is true of all fractions, due to simplification)

This contradicts that $a$ and $b$ have no common factors, thus $\sqrt{2}$ is irrational.