List Starting with GCD Propositions:
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 |
If a,b,q,r are integers such that
a = qb+r, then gcd(a, b) = gcd(b, r)
Let a, b be integers, not both zero, and d ∈ \(\mathbb{N}\)
If d | a and d | b,and |
Let a, b ∈ Z. Then d = gcd(a, b) can be computed, and there exist x , y ∈ \(\mathbb{Z}\)
such that d = ax + by.
Let a, b ∈ Z, not both zero, and d ∈ N.
If d = gcd(a, b)
then
d | a and d | b |
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.
Let a and b be integers. If gcd(a, b) = d \(\ne\) 0, then gcd( \(\frac{a}{d} , \frac{b}{d}\) ) = 1.
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.
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.
Let p be a prime and a, b ∈ \(\mathbb{Z}\).
If p | (ab) then p | a or p | b.
There are infinitely many primes.
For every integer n > 1,
n can be written as a product of primes.
Let a, b ∈ \(\mathbb{Z}\) and gcd(a, b) = d.
The linear Diophantine equation ax + by = c has a solution iff d | c.
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}$$
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).
Let m ∈ \(\mathbb{N}\). Let a,b,c∈Z. Then
Let a ∈ \(\mathbb{Z}\) and m ∈ \(\mathbb{N}\).
Then there exists a unique integer 0 ≤ r < m such that a ≡ r (mod m).
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.
Let a,a′,b,b′ ∈Z. If a ≡ a′ (mod m)and b ≡ b′ (mod m), then
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).
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
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.
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)
Let a ∈ Z. Define
[a] = {x ∈ \(\mathbb{Z}\) : x ≡ a (modm)}
to be the congruence class of a modulo m.
Given a, b ∈ Z, i.e., [a], [b] ∈ \(\mathbb{Z_m}\),
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}\)]}
\([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).
If p is a prime number,a ∈ \(\mathbb{Z}\) and p \(\ne\) a,
then \(a^p−1\) ≡ 1 (mod p).
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}]\).
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\)).
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).
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.
A complex number in standard form is an expression of the form: x + yi where x , y ∈ R.
(a+bi)+(c+di)=(a+b)+(b+d)i
(a + bi)(c + di) = (ac − bd) + (ad + bc)i
The complex conjugate of z = x +yi (x,y ∈ R) is the complex number \(\bar{z}\) = x − yi.
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)
The modulus of z = x + yi (x, y ∈ R) is the non-negative real number |z| = |x + yi| = \(sqrt{x^2 + y^2}.\)
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)
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
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\))).
If θ ∈ R and n ∈ Z, then
\((cosθ+i sinθ)^n\) =(cos nθ+i sin nθ)
For notational convenience, we define
\(e^{iθ}\) = cos(θ) + i sin(θ)
for θ ∈ R.
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.
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))
Suppose f(x) ∈ F[x] and c ∈ F.
The remainder when the
polynomial f (x) is divided by x − c is f (c).