Flashcards: Number Theory Fundamentals — 20 cards

Division Algorithm — statement?

Unique $q, r$ with $a = dq + r$, $0 \\leq r < d$.

Divisibility — relation?

Exists $k$ with $b = ak$.

Linear combination — form?

$ax + by$, with integers $x, y$.

Quotients and Remainders — result?

From division: $a = bq + r$, with $0 \\leq r < b$.

Modular arithmetic — relation?

$a \\equiv b \\ ( ext{mod } m)$ if $m$ divides $a - b$.

Prime number — definition?

Divisible only by 1 and itself.

Prime factorization — theorem?

Unique product of primes for each integer > 1.

GCD — meaning?

Largest divisor common to two numbers.

Euclid's Algorithm — purpose?

Efficient GCD computation via division.

Extended Euclidean Algorithm — finds?

GCD and coefficients for $ax + by = \\gcd(a, b)$.

Multiplicative inverse — condition?

Exists if and only if $a$ and $m$ are coprime.

Division Algorithm — applies to?

All integers, positive divisor.

Divisibility — extended to?

Linear combinations; divisibility of sums.

Prime numbers — importance?

Building blocks of integers.

Prime factorization — uniqueness?

Yes, up to order.

GCD — computed by?

Prime factorization or Euclid's Algorithm.

Modular arithmetic — properties?

Addition, subtraction, multiplication preserve congruence.

Linear combination — purpose?

Express GCD as $ax + by$.

Inverse — exists when?

When $\\gcd(a, m) = 1$.

Key concept — in number theory?

Prime factorization and divisibility.