Instructor: Dr. Daniel Saracino
Date: From 2024-08-29 to 2024-12-20

For a printable pdf file, please click here

Theorem 1

For all integers $a$, $b$, $c$, $d$:

1. If $a \mid b$ and $b \mid c$, then $a \mid c$.
2. If $a \mid b$ and $a \mid c$, then for all $x, y \in \mathbb{Z}$, $a \mid (xb + yc)$.
3. If $a \mid b$ and $c \mid d$, then $ac \mid bd$.

Theorem 2

Suppose $a$ and $b$ are integers that are not both 0, so that $(a, b)$ exists.
Then for every $n \in \mathbb{Z}$,

Theorem 3

Every integer $n \ge 2$ is the product of one or more primes.

Theorem 4

There exist infinitely many primes.

Theorem 5

For every integer $n \ge 2$, the factorization of $n$ into primes is unique, except for the order in which the factors are written.

Theorem 6

Suppose $m \in \mathbb{Z}^+$ and $a, b \in \mathbb{Z}$.
Then the following are equivalent:

1. $a \equiv b \ (\text{mod}\ m)$, i.e., $m \mid (a - b)$.
2. $a = b + m\ell$ for some $\ell \in \mathbb{Z}$.
3. $\overline{a}^m = \overline{b}^m$. ¹

Thus, the remainders are equal, and any one of (i), (ii), or (iii) proves the other two.

Theorem 7

Basic Properties of Congruence Modulo $m$:

Suppose $m \in \mathbb{Z}^+$, then the following all hold:

1. Reflexivity: For every $a \in \mathbb{Z}$,
   $a \equiv a \ (\text{mod}\ m)$.

2. Symmetry: For all $a, b \in \mathbb{Z}$,
   if $a \equiv b \ (\text{mod}\ m)$, then $b \equiv a \ (\text{mod}\ m)$.

3. Transitivity: For all $a, b, c \in \mathbb{Z}$,
   if $a \equiv b \ (\text{mod}\ m)$ and $b \equiv c \ (\text{mod}\ m)$, then $a \equiv c \ (\text{mod}\ m)$.

When a relationship between elements of a set $S$ is reflexive, symmetric, and transitive, the relationship is called an equivalence relation on $S$.

Thus, Theorem 7 says that "congruence modulo $m$" is an equivalence relation on the set $\mathbb{Z}$.

Theorem 8

Suppose $m \in \mathbb{Z}^+$, and let $a, b, c, d \in \mathbb{Z}$.
Then, if $a \equiv b \ (\text{mod}\ m)$ and $c \equiv d \ (\text{mod}\ m)$, we have:

1. $a + c \equiv b + d \ (\text{mod}\ m)$
2. $ac \equiv bd \ (\text{mod}\ m)$
3. Let $m \in \mathbb{Z}$ and $a, b, c \in \mathbb{Z}$.

Then

if and only if

Theorem 9

The congruence $ax \equiv b \pmod{m}$ has solutions if and only if $(a,m) \mid b$.
If $(a,m)\mid b$ then there is a unique solutions $x_0$ such that $0 \le x_0 < \frac{m}{(a,m)}$, and a complete set of solutions $\pmod{m}$ is

Chinese Remainder Theorem/CRT

Suppose $b_1, \cdots, b_n \in \mathbb{Z}$ and $m_1, \cdots, m_n \in \mathbb{Z}^+$.

Consider the system

If $m_1, \cdots, m_n$ are pairwise relatively prime, meaning $(m_i, m_j)=1$ where $i \neq j$, then the system has a solution.

And all the solutions are $\equiv \pmod{m_1 * m_2 * \cdots * m_n}$

Fermat's Little Theorem(1640)

Let $p$ be prime then:

1. If $a \in \mathbb{Z}$ and $(a, p)=1$, then $a^{p-1}=1 \pmod{p}$

2. For all integers $a$, $a^p \equiv a \pmod{p}$

Wilson's Theorem

For every prime $p$, $(p-1)! \equiv -1 \pmod{p}$

Euler's Theorem

If $a \in \mathbb{Z}$ and $(a,n)=1$ then

Notice how $a$ can be any number coprime to $n$

If $n \ge 2$ and the prime power decomposition of $n$ is $n = p_1^{e_1} \times \cdots \times p_k^{e_k}$ then

e.g,

Theorem 11

If $n$ is composite, then $n$th Mersenne number is composite.

Fermat's Mersenne Test

If $p$ is an odd prime, then every prime factor $q$ of $M_p$ has the form $q=2kp+1$ for some $k \in \mathbb{Z}^+$

Perfect Number

$n$ is perfect if and only if $\sigma(n) = 2$

For every prime p,

Theorem 12

$\sigma$ is multiplicative

Euclid's Theorem on Perfect Numbers

If $n$ is an even perfect number, then there exists a Mersenne prime $2^p-1$ such that

i.e., all even perfect numbers comes from $n=2^{p-1}(2^p-1)$

Theorem 13

Suppose $f: S \rightarrow T$ and $g: T \rightarrow U$ Then:

1. If $f$ and $g$ are both one-to-one, then so is $g \circ f$
2. If $f$ and $g$ are both onto, then so is $g \circ f$

Theorem 14: Intervals Theorem

Suppose $a < b$ where $a, b \in \mathbb{R}$ Then:

1. $(a,b) \sim (c,d)$ for all $c < d$ in $\mathbb{R}$
2. $(a,b) \sim (c, \infty)$ for all $c \in \mathbb{R}$
3. $(a, b) \sim \mathbb{R}$

Theorem 15

The set of real numbers in the interval $(0, 1)$ is uncountable(equivalently, $\mathbb{R}$ is uncountable)

Theorem 16

If $B$ is countable, and $f: A \rightarrow B$ is an injection, then $A$ is countable.

Theorem 17

If $A_1, \cdots , A_k$ are finitely many countable sets, then $A_1 \times A_2 \times \cdots \times A_k$ is countable.

Theorem 18

the union of countably many countable sets are countable.

i.e., the union of countable collection of countable sets is countable.

note: the ®sets are allowed to overlap.

Lemma: Bezout's Lemma

If $m$ and $n$ are integers that are not both zero, such that $(m, n)$ exists,
then there exist $x, y \in \mathbb{Z}$ such that $xm + yn = (m, n)$.

Lemma: Euclid's Lemma

Suppose $a$, $b$, $c$ are integers such that $a \mid bc$ and $(a, b) = 1$.
Then $a \mid c$.

Lemma: Division Lemma

If $a$ and $m$ are integers and $m$ is positive, then there exist integers $q$ and $r$ such that $a = qm + r$ and $0 \le r \le m$

Lemma: How to check if a congruence is solvable

The congruence $ax \equiv b \pmod{m}$ is solvable if and only if

Then there is a unique solution $x_0$ such that

Then the complete set of solutions is

There are exactly $(a,m)$ incongruent solutions $\mod{m}$

Lemma:

If $S$ and $T$ are finite sets with the same number of elements, and $f: S \rightarrow T$, then $f$ is one-to-one if and only if $f$ is onto.

Lemma:

If $x$ is a nonempty countable set, then there exists an injection $f: x \rightarrow \mathbb{Z}^+$

Lemma:

If $S \subseteq \mathbb{Z}^+$, then $S$ is countable.

Definitions

Coprime

We say integers $a$ and $b$ are relatively prime (or "coprime") if $(a, b) = 1$.

Prime

An integer $p$ is prime if $p > 1$ and the only positive integers that divide $p$ are $1$ and $p$.

Euler's Function

e.g,

Mersenne Numbers

If $n \in \mathbb{Z}^+$, the $n$th Mersenne number is $2^n-1$

Proper Factors

If $n \in \mathbb{Z}^+$, the proper factors of $n$ are the positive integers that divide $n$ but are not $n$.

Perfect Numbers

A positive integer is called perfect if it equals the sum of its proper factors.

$\sigma(n)$

If $n \in \mathbb{Z}^+$, then $\sigma(n)$ denotes the sum of all positive integers that divide $n$.

Function

We say $f$ is a function(or mapping) from $S$ to $T$ and we write

if $f$ associates to each $s \in S$ a uniquely determined element $f(s) \in T$

One-to-one: Injection

If $f: S \rightarrow T$ we say $f$ is one-to-one(or "1-1")

1. if whenever $s_1 \neq s_2$ in $S$, then $f(s_1) \neq f(s_2)$ in $T$.
2. if and only if when $s_1, s_2 \in S$ and $f(s_1) = f(s_2), then s_1=s_2$.

Onto: Surjection

If $f: S \rightarrow T$ we say $f$ is onto if for every $t \in T$ there exists some $s \in S$ such that $f(s)=t$.

Bijection

$f$ is a bijection if $f$ is both one-to-ton and onto. When a function is a bijection, there is an inverse function and the domain eqals codomain.

Inverse Function

Suppose $f: S \rightarrow T$ is a bijection. Then for each $t \in T$ there is a unique $s \in S$ such that $f(s) = t$. So we can define a function $f^{-1}: T \rightarrow S$ by letting.

$f^{-1}$ is the inverse function of $f$.

Powerset

If $x$ is a set, then the powerset $x$ is the set whose elements are the subsets of $x$. We denote the powerset of $x$ by $P(x)$

So $P(x) = \{A | A \le x\}$

e.g., If $x = \{1, 2\}$, $P(x) = \{\emptyset, \{1\}, \{2\}, \{1, 2\} \}$

Number of Elements in a Finite Set: $|x|$

Cartesian Product

If $A$ and $B$ are sets, their cartesian product is the set $A \times B = \{(a,b) | a \in A \text{and} b \in B\}$

Note that if $A$ and $B$ are finite sets, then

Composite Functions

If $f: S \rightarrow T$ and $g: T \rightarrow U$, we define the composite function $g \circ f: S \rightarrow U$ by letting

for all $s \in S$

Corollary 1

Every integer $n \ge 2$ has a unique representation in the form:

where the $p$'s are distinct primes and each $e_i \ge 1$. This is called the prime-power decomposition of $n$.

Corollary 2

Suppose $n \ge 2$ and the prime-power decomposition (ppd) of $n$ is:

Then if $m$ is any positive integer that divides $n$,

for some integers $f_1, \cdots, f_k$ such that $0 \le f_i \le e_i$.

Corollary 3

If

and

where $p_1, \cdots, p_k$ are distinct primes, and the $c_i$'s and $d_i$'s are nonnegative integers, then

Corollary 4

If $n$ is an integer such that $n \ge 2$, then there exists a positive integer $m$ such that $n = m^2$ if and only if all the exponents in the ppd of $n$ are even.

Corollary 5: Theorem 8-1

Suppose $a \equiv b \ (\text{mod}\ m)$. Then:

• $a \equiv b \ (\text{mod}\ m)$
• $a^2 \equiv b^2 \ (\text{mod}\ m)$
• $a^3 \equiv b^3 \ (\text{mod}\ m)$
• ...
• $a^k \equiv b^k \ (\text{mod}\ m)$ for every $k \in \mathbb{Z}^+$.

Thus, using part (ii) of Theorem 8 repeatedly, we get:

If $a \equiv b \ (\text{mod}\ m)$, then $a^k \equiv b^k \ (\text{mod}\ m)$ for every $k \in \mathbb{Z}^+$.

Corollary 6: Theorem 8-2

If $p(x)$ is a polynomial with integer coefficients and $a \equiv b \ (\text{mod}\ m)$, then $p(a) \equiv p(b) \ (\text{mod}\ m)$.

$\varphi(n)$ Corollary

If $n \ge 3$, then $\varphi(n)$ is even.

For $n = 1 \text{ or } 2$, $\varphi(n) = 1$

If $p \mid n$, then $(p-1) | \varphi(n)$

Corolllary of Theorem 12

If the prime power decomposition of $n$ is

then

Corolllary of Theorem 16

Subsets of countable sets are countable.

Sidenote 1: $(a-m)x \equiv b \pmod{m}$

Given $ax \equiv b \pmod{m}$, since $a-(a-m) = m$,

In modular arithmetic, any integer is equivalent to itself plus or minus any multiple of the modulus.

so

Thus

Sidenote 2

Every integer is congruent$\pmod{9}$ to one of $\{0, 1, 2, \cdots, 8\}$