Shreyas’ Notes

# MATH 365

## Divisibility §

Theorem: For integers $a$, $b$, $c$, the following hold:

• $a \mid 0$, $1 \mid a$, $a \mid a$, $\pm a \mid \pm a$

• $a \mid 1$ iff $a = \pm 1$

• if $a \mid b$ and $c \mid d$, $ac \mid bd$

• if $a \mid b$ and $b \mid c$, $a \mid c$

• if $a \mid b$ and $b \mid a$, $a = \pm b$

• if $a \mid b$ and $b \neq 0$, $|a| \leq |b|$

• if $a \mid b$ and $a \mid c$, $a \mid (bx + cy)$ for all $x, y \in \mathbb{Z}$

if $x + y = z$ and $a$ divides any two of $x, y, z$, then $a$ also divides the other number

GCD: for $a, b \in \mathbb{Z}$, the GCD is the largest integer that divides both $a$ and $b$. aka the unique integer $d$ such that: $d \mid a$, $d \mid b$, and $c \mid a \wedge c \mid b \implies c \leq d$.

well-ordered principle:

• any non-empty $S \subseteq \mathbb{N}$ has a least element
• any non-empty $S \subseteq \mathbb{Z}$ bounded above/below a greatest/least element

if $\gcd(a, b) = 1$, $a$ and $b$ are relatively prime (coprime).

Given $a, b \in \mathbb{Z}$ st $b \neq 0$, there exist unique integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < |b|$.

Bezout’s Theorem: Let $a, b \in \mathbb{Z}$ such that they’re not both zero. $\gcd(a, b)$ is the smallest positive integer $d$ that can be written in the form $d = ax + by$ with $x, y \in \mathbb{Z}$.

If $c$ is a common divisor of $a$ and $b$, $c \mid \gcd(a, b)$

Multiples of $\gcd(a, b)$ are precisely the integers of the form $ax + by$ for $x, y \in \mathbb{Z}$. In other words, $ax + by = c$ has a solution iff $\gcd(a, b) \mid c$.

$a$ and $b$ are relatively prime iff there exist $x, y \in \mathbb{Z}$ such that $ax + by = 1$.

If $\gcd(a, b) = d$, $\gcd\left(\frac{a}{d}, \frac{b}{d}\right) = 1$.

If $a \mid b$, $b \mid c$, and $\gcd(a, b) = 1$, then $ab \mid c$.

Euclid’s Lemma: If $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$.

If $p$ is prime and $p \mid ab$, then $p \mid a \vee p \mid b$.

$\gcd(a, b) = \gcd(a + bq, b)$

Euclid’s Algorithm: Let $a, b \in \mathbb{Z}$ st they’re not both zero. $r_{-1} = a$, $r_0 = b$. $r_{i + 1}$ is the remainder of the division algorithm applied to $r_{i-1}$ and $r_i$.

Linear equation theorem: Let $a, b$ be non-zero integers with $d = \gcd(a, b)$. $ax + by = d$ always has an integer solution $(x_0, y_0)$ which can be found using the extended Euclid’s algorithm. All other solutions are of the form $\left(x_0 + k \frac{b}{d}, y_0 - k \frac{a}{d}\right)$ for $k \in \mathbb{Z}$.

Linear equations where solutions must be integers are called diophantine equations.

If $p$ is prime and $p \mid a_1 a_2 \dots a_n$, then $p \mid a_k$ for some $k$, $1 \leq k \leq n$.

If $p, q_1, q_2, \dots, q_n$ are prime and $p \mid q_1 q_2 \dots q_n$, then $p = q_k$ for some $k$, $1 \leq k \leq n$.

Every positive integer ($n > 1$) can be expressed as a product of primes $n = p_1 p_2 \dots p_n$. This representation is unique up to the order of primes.

Any positive integer $n > 1$ can be written canonically as $n = p_1^{a_1} \dots p_r^{a_r}$ where $p_1 < \dots < p_r$ are prime and $0 < a_1, \dots, a_n$.

There are infinitely many primes.

Prime Number Theorem: The function $\pi$ is asymptotic to $\frac{x}{\ln x}$.

The proportion of primes at most $n$ is $~ \frac{1}{\ln n}$.

Goldbach Conjecture: Every even number $n \geq 4$ can be written as the sum of two primes.

Twin Prime Conjecture: There are infinitely many primes $p$ such that $p + 2$ is also prime.

A pythagorean triplet is an integer solution to the equation $x^2 + y^2 = z^2$. A pythagorean triple is called primitive if $\gcd(x, y, z) = 1$.

The least common multiple of $a, b \in \mathbb{N}$ is the smallest positive integer $n$ such that $a \mid n$ and $b \mid n$.

$\gcd(a, b) = \prod_{\text{primes }p} p^{\min(a_p, b_p)}$

$lcm(a, b) = \prod_{\text{primes }p} p^{\max(a_p, b_p)}$

$ab = \prod p^{a_p + b_p} = \prod p^{\min(a_p, b_p) + \max(a_p, b_p)} = \gcd(a, b) \cdot lcm(a, b)$

For a given $m \in \mathbb{N}$, two integers $a, b$ are congruent modulo $m$ if $m \mid a - b$.

$a \equiv b \mod m$

Every integer is congruent modulo $m$ to precisely one integer $a$ where $0 < a < m$.

The set of integers $0, 1, 2, \dots, m - 1$ is called the least residue system modulo $m$.

$a_1, a_2, \dots, a_m$ is a complete residue system modulo $m$ if every integer is congruent modulo $m$ to precisely one of $a_i$.

$a \equiv b \mod m$ iff $a$ and $b$ leavea the same remainder when divided by $m$.

Equivalence relation.

• reflexive: $a \equiv a \mod m$
• symmetric: if $a \equiv b \mod m$, then $b \equiv a \mod m$
• transitive: if $a \equiv b \mod m$, $b \equiv c \mod m$, then $a \equiv c \mod m$

for a given $m \in \mathbb{N}$, $a, b, c, d \in \mathbb{Z}$:

• if $a \equiv b \mod m$ and $c \equiv d \mod m$, then $a \pm c \equiv b \pm d \mod m$
• if $a \equiv b \mod m$ and $c \equiv d \mod m$, then $ac \equiv bd \mod m$
• if $a \equiv b \mod m$, then $a + c \equiv b + c \mod m$ and $ac = bc \mod m$.
• if $a \equiv b \mod m$, then $a^n \equiv b^n \mod m$ for all $n \in \mathbb{N}$