1. Getting started some foundational material

1.1 About this chapter (no points)

1.2 The Division Algorithm

Integer division: input and output values must always be integers

Definition 1.2.1: Divides

• $x\mid y$: $x$ divides $y$
• $x\nmid y$: $x$ does not divide $y$
• $x\mid y⟺x\ne 0$ and $y=kx$ for some $k\in \mathbb{Z}$
• If $x\mid y$, then:
  • $y$ is a multiple of $x$
  • $x$ is a factor (or divisor) of $y$

Linear combination of two numbers: the sum of multiples of those numbers

Theorem 1.2.1: Divisibility and linear combinations

• Let $x,y,z\in \mathbb{Z}$
• If $x\mid y$ and $x\mid z$, then:
  • $x\mid (sy+tz)$ for any $s,t\in \mathbb{Z}$
  • If $x$ divides both $y$ and $z$, then $x$ divides any integer linear combination of $y$ and $z$

Proof 1.2.1: Divisibility and linear combinations

• Since $x\mid y$, then $y=kx$ for some $k\in \mathbb{Z}$
• Since $x\mid z$, then $z=jx$ for some $j\in \mathbb{Z}$
• For any $s,t\in \mathbb{Z}$:
  • $sy+tz=s(kx)+t(jx)=(sk+tj)x$
  • Since $sk+tj\in \mathbb{Z}$, $sy+tz$ is an integer multiple of $x$
  • Therefore, $x\mid (sy+tz)$

Theorem 1.2.2: The Division Algorithm

• Let $n\in \mathbb{Z}$ and let $d\in {\mathbb{Z}}^{+}$
• Then there exist unique integers $q,r\in \mathbb{Z}$ such that:
  • $n=qd+r$
  • $0\le r\le d-1$

Definition 1.2.2: Integer division definitions

• Integer Division:
  • $q$ is called the quotient
  • $r$ is called the remainder
• The operations $\mathrm{div}$ and $\mathrm{mod}$ produce the quotient and remainder:
  • $q=n\mathrm{div}d$
  • $r=n\mathrm{mod}d$

1.3 Prime factorization

Prime: an integer greater than 1 and its only factors are 1 and itself
Composite: a positive integer has a factor other than 1 or itself

Theorem 1.3.1: The Fundamental Theorem of Arithmetic

Every positive integer other than 1 can be expressed uniquely as a product of prime numbers where the prime factors are written in nondecreasing order

Multiplicity of a prime factor p in a prime factorization: number of times p appears in the product of primes

Definition 1.3.1: Greatest common divisor and least common multiple

• Greatest common divisor (GCD):

  • For integers $x$ and $y$ that are not both zero, $\gcd (x,y)$ is the largest positive integer that divides both $x$ and $y$
  • $\gcd (x,y)\mid x$ and $\gcd (x,y)\mid y$

• Least common multiple (LCM):

  • For nonzero integers $x$ and $y$, $\mathrm{lcm}(x,y)$ is the smallest positive integer that is a multiple of both $x$ and $y$
  • $x\mid \mathrm{lcm}(x,y)$ and $y\mid \mathrm{lcm}(x,y)$

Relatively prime: the greatest common divisor of the two numbers is 1

Theorem 1.3.2: GCD and LCM from prime factorizations

• Let $x$ and $y$ be positive integers with prime factorizations:

  • $x=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r}$
  • $y=p_1^{{\beta }_1}\cdot p_2^{{\beta }_2}\cdots p_r^{{\beta }_r}$
  • $p_1,p_2,\dots ,p_r$ are distinct prime numbers.
  • ${\alpha }_i,{\beta }_i\in {\mathbb{Z}}_{\ge 0}$

• Divisibility:

  • $x\mid y⟺{\alpha }_i\le {\beta }_i$ for all $1\le i\le r$

• GCD:

  • Take the minimum exponent of each prime.
  • $\gcd (x,y)=p_1^{\min \{{\alpha }_1,{\beta }_1\}}\cdot p_2^{\min \{{\alpha }_2,{\beta }_2\}}\cdots p_r^{\min \{{\alpha }_r,{\beta }_r\}}$

• LCM:

  • Take the maximum exponent of each prime.
  • $\mathrm{lcm}(x,y)=p_1^{\max \{{\alpha }_1,{\beta }_1\}}\cdot p_2^{\max \{{\alpha }_2,{\beta }_2\}}\cdots p_r^{\max \{{\alpha }_r,{\beta }_r\}}$

1.4 Floor and ceiling functions

• Floor Function:

  • $\lfloor x\rfloor$ maps $x\in \mathbb{R}$ to the nearest integer in the downward direction.
  • $\lfloor x\rfloor =\max \{y\in \mathbb{Z}\mid y\le x\}$
  • Equivalently: $\lfloor x\rfloor \le x<\lfloor x\rfloor +1$

• Ceiling Function:

  • $\lceil x\rceil$ maps $x\in \mathbb{R}$ to the nearest integer in the upward direction.
  • $\lceil x\rceil =\min \{y\in \mathbb{Z}\mid x\le y\}$
  • Equivalently: $\lceil x\rceil -1<x\le \lceil x\rceil$

1.5 Logarithms and exponents

Divide-and-conquer: breaking a problem into smaller parts, solving each part, then combining the solutions

• Dividing Piles and the Logarithm Function:
  • Let $n,b\in {\mathbb{Z}}^{+}$ with $b>1$.
  • If each step replaces $n$ with $\lfloor \frac{n}{b}\rfloor$ until $n<b$:
    • Number of steps $=\lfloor {\log }_{b}n\rfloor$
  • If each step replaces $n$ with $\lceil \frac{n}{b}\rceil$ until $n=1$:
    • Number of steps $=\lceil {\log }_{b}n\rceil$

1.6 Number representation (optional)