List Starting with GCD Propositions:

## GCD

The greatest common divisor of integers a and b,
where a $$\ne$$ 0 or b $$\ne$$ 0, is an integer d $$\gt$$ 0 such that

•  d a, d b, and
•  for all c ∈ $$\mathbb{Z}$$, if c a and c | b, then c $$\le$$ d

## GCD with Remainders (GCD WR)

If a,b,q,r are integers such that
a = qb+r, then gcd(a, b) = gcd(b, r)

## GCD Characterization Theorem (GCD CT)

Let a, b be integers, not both zero, and d ∈ $$\mathbb{N}$$

•  If d a and d b,and
• There exist x, y ∈ $$\mathbb{Z}$$ such that d = ax+by
Then d = gcd(a, b).

## EEA (EEA Theorem (a.k.a Bezout’s Lemma))

Let a, b ∈ Z. Then d = gcd(a, b) can be computed, and there exist x , y ∈ $$\mathbb{Z}$$
such that d = ax + by.

## EEA shows converse of GCD CT is true

Let a, b ∈ Z, not both zero, and d ∈ N.
If d = gcd(a, b)
then

•  d a and d b
• There exist x, y ∈ $$\mathbb{Z}$$ such that d = ax+by.

## GCD of One (GCD OO)

Let a and b be integers.
Then gcd(a, b) = 1
if and only if there exist integers x and y with ax + by = 1.

## GCD DB (DB GCD))

Let a and b be integers. If gcd(a, b) = d $$\ne$$ 0, then gcd( $$\frac{a}{d} , \frac{b}{d}$$ ) = 1.

## Coprime

We say integers a and b are coprime if and only if gcd(a, b) = 1.

Let a, b, c ∈ $$\mathbb{Z}$$. If c | ab and gcd( a , c ) = 1, then c | b.

## Primes

An integer p > 1 is said to be a prime if and only if the only positive divisors of p are 1 and p itself.

## Primes and Divisibilty

Let p be a prime and a, b ∈ $$\mathbb{Z}$$.
If p | (ab) then p | a or p | b.

## (Infinitely Many Primes (INF P))

There are infinitely many primes.

## (Prime Factorization (PF))

For every integer n > 1,
n can be written as a product of primes.

## Linear Diophantine Equation 1 (LDE1)

Let a, b ∈ $$\mathbb{Z}$$ and gcd(a, b) = d.
The linear Diophantine equation ax + by = c has a solution iff d | c.

## Linear Diophantine Equation 2 (LDE2)

Let gcd(a,b) = d where a $$\ne$$ 0 and b $$\ne$$ 0 are integers.
If x = $$x_0$$ and y = $$y_0$$ is one particular integer solution to the linear diophantine equation ax + by = c,

## Proposition (DAP)

If f (x), g(x) ∈ F[x] and g(x) is not the zero polynomial, then there exist unique polynomials q(x), r(x) ∈ F[x]
such that f (x) = q(x)g(x) + r(x) with r(x) being the zero polynomial or deg(r(x)) < deg(g(x))

## Remainder Theorem (RT)

Suppose f(x) ∈ F[x] and c ∈ F.
The remainder when the
polynomial f (x) is divided by x − c is f (c).