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.
Coprimes and Divisibility (CAD)
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,
then the complete integer solution is
x = \(x_0\) + \(\frac{b}{d}n\), y = \(y_0\)−\(\frac{a}{d}n, ∀ n ∈\)\mathbb{Z}$$
Congruence
Let m be a fixed positive integer.
If a, b ∈ \(\mathbb{Z}\) we say that a is congruent to b modulo m
if and only if m  (a − b).
Congruence is an Equivalent Relation
Let m ∈ \(\mathbb{N}\). Let a,b,c∈Z. Then
 a ≡ a (mod m). (reflexivity)
 a ≡ b (mod m)⇒ b ≡ a (mod m). (symmetry)
 a ≡ b (mod m) and b ≡ c (mod m)⇒ a ≡ c (mod m). (transitivity)
Unique Remainder
Let a ∈ \(\mathbb{Z}\) and m ∈ \(\mathbb{N}\).
Then there exists a unique integer 0 ≤ r < m such that a ≡ r (mod m).
Congruent If and Only If Remainder
Let m ∈ N, a, b ∈ Z. Then a ≡ b (mod m) if and only if a and b have the same remainder when divided by m.
Properties of Modular Congruence
Let a,a′,b,b′ ∈Z. If a ≡ a′ (mod m)and b ≡ b′ (mod m), then
 a + b ≡ a′+ b′ (mod m)
 a − b ≡ a′− b′ (mod m)
 ab ≡ a′b′ (mod m)
Congruence and Division
Let a,b,c ∈ Z, m ∈ N and c \(\ne\) 0 (mod m).
If ac ≡ bc (mod m) and gcd(c,m)=1,then a≡b (mod m).
Linear Congruence
Given m ∈ \(\mathbb{N}\) and a,c ∈ \(\mathbb{Z}\), the relation ax ≡ c (mod m),
where x is a variable, is called a linear congruence.
We wish to find (i.e., solve for) all integer values of x
Brute Force vs. EEA:
Solve 5x ≡ 3 (mod 7).
Exercise: can use CISR and trial and error to get \(x_0\) = 2
and then PC to deduce x ≡ 2 (mod 7).
Solution: Convert 5x ≡ 3 (mod 7) into the LDE 5x + 7y = 3. Use the EEA table to solve.
Linear Congruence Theorem Version 1 (LCT 1)
Let gcd(a, m) = d \(\ne\) 0.
The linear congruence ax ≡ c (mod m) has a solution if
and only if d  c.
Moreover, if x = \(x_0\) is one particular solution, then the
complete solution is x ≡ \(x_0\) (mod m)
Congruence Class
Let a ∈ Z. Define
[a] = {x ∈ \(\mathbb{Z}\) : x ≡ a (modm)}
to be the congruence class of a modulo m.
Arithmetic Operations for Congruence Classes
Given a, b ∈ Z, i.e., [a], [b] ∈ \(\mathbb{Z_m}\),
 Addition: [a]+[b] = [a + b ]
 Subtraction: [a] − [b] = [a − b]
 Multiplication: [a] · [b] = [a · b].
We do not directly define division.
Linear Congruence Theorem, Version 2 (LCT 2)
Let gcd(a, m) = d \(\ne\) 0.
The equation [a][x] = [c] in \(\mathbb{Z_m}\) has a solution if and only if d  c.
Moreover, if [x] = [x0] is one particular solution, then the complete solution is
{[\(x_0\)],[\(x_0\) + m],[\(x_0\) +2m],…,[\(x_0\) +(d −1)\(\frac{m}{d}\)]}
Existence of Inverses
\([a]^−1\) exists in \(\mathbb{Z_m}\) iff gcd(a, m) = 1
The inverse of [a] in \(\mathbb{Z_m}\) is unique (if it exists).
Fermat’s Little Theorem (FLT)
If p is a prime number,a ∈ \(\mathbb{Z}\) and p \(\ne\) a,
then \(a^p−1\) ≡ 1 (mod p).
Corollaries to FLT
If p is a prime number,and a ∈ Z,then \(a^p\) ≡ a (mod p)
If p is a prime number and [a] \(\ne\) [0] in \(\mathbb{Z_p}\),
then \([a]^{−1}\) = \([a^{p−2}]\).
Chinese Remainder Theorem
If gcd(\(m_1\), \(m_2\)) = 1, then for any choice of integers \(a_1\) and \(a_2\), there exists a solution to the simultaneous congruences
n ≡ \(a_1\) (mod \(m_1\))
n ≡ \(a_2\) (mod \(m_2\))
Moreover, if n = \(n_0\) is one integer solution, then the complete solution is n ≡ \(n_0\) (mod \(m_1m_2\)).
Proposition (Splitting Modulus (SM))
Let p and q be coprime positive integers. Then for any two integers x and a,
x ≡ a (mod p)
x ≡ a (mod q)
⇐⇒ x ≡ a (mod pq).
RSA
Proposition (RSA)
Let p, q be primes with p \(\ne\) q.
All variables introduced below are integers.
Let n = pq and φ(n)=(p−1)(q−1).
Let1<e,d<φ(n)
such that ed≡1 (mod(p−1)(q−1)).
Let 0 ≤M<n.
If 0 ≤ C< n such that \(M^e\) ≡C (mod n) and
0 ≤ R<n such that \(C^d\) ≡ R (mod n),
then R = M.
Complex Numbers
A complex number in standard form is an expression of the form: x + yi where x , y ∈ R.
Addition:
(a+bi)+(c+di)=(a+b)+(b+d)i
Complex Multiplication:
(a + bi)(c + di) = (ac − bd) + (ad + bc)i
Complex Conjugate
The complex conjugate of z = x +yi (x,y ∈ R) is the complex number \(\bar{z}\) = x − yi.
Properties of Conjugate (PCJ)
If z and w are complex numbers, then
\(\bar{z+w}\) = \(\bar{z}+\bar{w}\)
\(\bar{zw}\) = \(\bar{z}\bar{w}\)
\(\bar{(\bar{z})}\) = z
z+\(\bar{z}\) =2R(z)
z−\(\bar{z}\) =2iI(z)
Modulus
The modulus of z = x + yi (x, y ∈ R) is the nonnegative real number z = x + yi = \(sqrt{x^2 + y^2}.\)
Properties of Modulus
If z,w ∈ C, then z=0 iff z=0 z = z \(\bar{z}\)z=z2 zw = zw z + w ≤ z + w. (This is called the triangle inequality)
Polar Form
r = \(\sqrt{x^2 + y^2}\) (distance from origin)
and θ is an angle (measured counterclockwise from
positive xaxis) such that:
r cos θ = x
r sin θ = y
Polar Form Multiplication
If \(z_1\) =\(r_1\)(\(cosθ_1+i sinθ_1\))and \(z_2\) =\(r_2\)(\(cosθ_2+isinθ_2\)) are two complex numbers in polar form, then
\(z_1 z_2\) = r1r2(cos(θ1 + θ2) + i sin(\(θ_1 + θ_2\))).
De Moivre’s Theorem
If θ ∈ R and n ∈ Z, then
\((cosθ+i sinθ)^n\) =(cos nθ+i sin nθ)
Exponentiation
For notational convenience, we define
\(e^{iθ}\) = cos(θ) + i sin(θ)
for θ ∈ R.
Complex Nth Roots Theorem
Proposition (CNRT)
Suppose w is a nonzero complex number written in its polar form as w = r [cos(θ) + i sin(θ)].
Then there are exactly n distinct complex solutions to zn = w, labeled z0,z1,…,zn−1 whose polar forms are given by
\(z_k\) = \(sqrt[n]{r}\)[cos(\(\frac{θ+2πk}{n}\)+ i sin(\(\frac{θ+2πk}{n}\))]
for k = 0,1,…,(n−1), and \(sqrt[n]{r} is the real, positive,\)n^th$$ root of r.
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).