FoldUnfold Table of Contents Prime and Composite Numbers, Modular Arithmetic Review Prime and Composite Numbers, Modular Arithmetic Review We will now review some of the recent material regarding prime numbers, composite numbers, and modular arithmetic. On the Prime and Composite Numbers we formally defined what it means for a number to be prime or composite. We said … [Read more...]

## Modular Arithmetic

FoldUnfold Table of Contents Modular Arithmetic Modular Arithmetic Definition: If $a, b, m \in \mathbb{Z}$ then we say that $a$ is Congruent to $b$ modulo $m$ denoted $a \equiv b \pmod m$ if $m \mid (a - b)$. The congruence of two integers is an equivalence relation which we can describe in other words. We say that $a$ and $b$ are said to be congruent modulo $m$ if … [Read more...]

## The Unique Prime Factorization Theorem

FoldUnfold Table of Contents The Unique Prime Factorization Theorem The Unique Prime Factorization Theorem We will now look at a very important theorem which says that any integer $n > 1$ can be written uniquely as a product of primes $p_1, p_2, ..., p_k$: (1) \begin{align} \quad n = p_1p_2...p_k \end{align} Theorem 1 (The Unique Prime Factorization Theorem): If $n \in … [Read more...]

## Euclid’s Theorem of the Existence of Infinitely Many Primes

FoldUnfold Table of Contents Euclid's Theorem of the Existence of Infinitely Many Primes Euclid's Theorem of the Existence of Infinitely Many Primes Recall from the Prime and Composite Numbers page that an integer $p > 1$ is a prime number if the only divisors of $p$ are $\pm 1$ and $\pm p$, and an integer $p > 1$ that is not a prime number is called a composite … [Read more...]

## Prime and Composite Numbers

FoldUnfold Table of Contents Prime and Composite Numbers Prime Numbers Composite Numbers Prime and Composite Numbers Prime Numbers Definition: An integer $p > 1$ is said to be Prime if the only divisors of $p$ are $\pm 1$ and $\pm p$. For a long time it was debated whether the number $1$ should be classified as a prime number or not. The importance of $1$ being … [Read more...]

## Integer Divisibility Review

FoldUnfold Table of Contents Integer Divisibility Review Integer Divisibility Review We will now review some of the recent material regarding integer divisibility. On the The Well-Ordering Principle of the Natural Numbers that the Well-Order Principle for the set of natural numbers $\mathbb{N}$ states the following important fact: Every NONEMPTY subset of the natural … [Read more...]

## The Greatest Common Division Between Integers

FoldUnfold Table of Contents The Greatest Common Division Between Integers The Greatest Common Division Between Integers Definition: If $a, b \in \mathbb{Z}$ then the Greatest Common Divisor of $a$ and $b$ denoted $\gcd (a, b)$ or $(a, b)$ is an integer $d \in \mathbb{Z}$ such that: 1. $d \mid a$ and $d \mid b$. 2. If $c \in \mathbb{Z}$, $c \mid a$, and $c \mid b$ then … [Read more...]

## The Division Algorithm

FoldUnfold Table of Contents The Division Algorithm The Division Algorithm One rather important aspect of the divisibility of integers is that if $a, b \in \mathbb{Z}$ then $a$ can be written as the product of some quotient $q$ with $b$ plus a remainder $r$. For example, if $a = 11$ and $b = 3$, then $a = 3(b) + 2$ where $q = 3$ and $r = 2$. The following theorem known as … [Read more...]

## Integer Divisibility

FoldUnfold Table of Contents Integer Divisibility Integer Divisibility Definition: Let $a, b \in \mathbb{Z}$. Then $b$ is said to be Divisible by $a$, or, $a$ is said to Divide $b$ written $a \mid b$ if there exists a $q \in \mathbb{Z}$ such that $aq = b$. The number $a$ is said to be a Divisor of $b$ and $b$ is said to be a Multiple of $a$. If there does not exist an … [Read more...]

## The Well-Ordering Principle of the Natural Numbers

FoldUnfold Table of Contents The Well-Ordering Principle of the Natural Numbers The Well-Ordering Principle of the Natural Numbers We begin our look through abstract algebra with a rather simple theorem regarding the set of natural numbers known as The Well-Ordering Principle of the Natural Numbers. Consider the following set which we define to be the set of natural … [Read more...]