Number Theory and Cryptography

Vocabulary flashcards covering the fundamental concepts of number theory, including divisibility, integer representations, primality, and common divisors based on Chapter 4 notes.

Number Theory

The part of mathematics devoted to the study of the integers and their properties.

Divisibility

A property where for integers $a$ and $b$ with $a \neq 0$, $a$ divides $b$ if there exists an integer $c$ such that $b = ac$.

Division Algorithm

A theorem stating that if $a$ is an integer and $d$ a positive integer, then there are unique integers $q$ and $r$ with $0 \le r < d$, such that $a = dq + r$.

Dividend

The integer $a$ being divided in the division algorithm $a = dq + r$.

Divisor

The positive integer $d$ by which the dividend is divided in the division algorithm $a = dq + r$.

Quotient

The unique integer $q$ in the division algorithm, denoted as $q = a \text{ div } d$.

Remainder

The unique non-negative integer $r$ less than the divisor, denoted as $r = a \text{ mod } d$.

Congruence Modulo $m$

If $a$ and $b$ are integers and $m$ is a positive integer, $a$ is congruent to $b$ modulo $m$ if $m$ divides $a - b$, denoted as $a \equiv b \pmod{m}$.

Base $b$ Expansion

The unique representation of a positive integer $n$ in the form $n = a_k b^k + a_{k-1} b^{k-1} + \dots + a_1 b + a_0$ where each digit $a_j$ is less than $b$.

Binary Expansion

A base $2$ representation of an integer using only digits $0$ and $1$.

Octal Expansion

A base $8$ representation of an integer using the digits $\{0, 1, 2, 3, 4, 5, 6, 7\}$.

Hexadecimal Expansion

A base $16$ representation using digits $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F\}$, where letters $A$ through $F$ represent decimal numbers $10$ through $15$.

Prime

A positive integer $p > 1$ that is divisible only by $1$ and by itself.

Composite

A positive integer greater than $1$ that is not a prime.

Fundamental Theorem of Arithmetic

The principle that every positive integer greater than $1$ can be written uniquely as a prime or as the product of two or more primes in order of nondecreasing size.

Sieve of Eratosthenes

An algorithm used to find all primes not exceeding a specified positive integer by iteratively deleting multiples of primes starting from $2$.

Trial Division

A method of determining if a number $n$ is prime by checking if it is divisible by any integer $i \le \sqrt{n}$.

Mersenne Primes

Prime numbers of the form $2^p - 1$, where $p$ is also a prime number.

Greatest Common Divisor ($\text{gcd}(a, b)$)

The largest integer $d$ such that $d | a$ and $d | b$.

Relatively Prime

Two integers $a$ and $b$ are considered relatively prime if $\text{gcd}(a, b) = 1$.

Pairwise Relatively Prime

A set of integers $a_1, a_2, \dots, a_n$ where $\text{gcd}(a_i, a_j) = 1$ whenever $1 \le i < j \le n$.

Least Common Multiple ($\text{lcm}(a, b)$)

The smallest positive integer that is divisible by both integers $a$ and $b$.

Euclidean Algorithm

An efficient method for computing the greatest common divisor by repeatedly applying the property $\text{gcd}(a, b) = \text{gcd}(b, a \text{ mod } b)$ until the remainder is $0$.