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

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}\)

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

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

  1. a ≡ a (mod m). (reflexivity)
  2. a ≡ b (mod m)⇒ b ≡ a (mod m). (symmetry)
  3. 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

  1. a + b ≡ a′+ b′ (mod m)
  2. a − b ≡ a′− b′ (mod m)
  3. 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}\),

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 non-negative 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=|z|2 |zw| = |z||w| |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 counter-clockwise from positive x-axis) 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 N-th Roots Theorem

Proposition (CNRT) Suppose w is a non-zero 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).

List of Propositions | Home