Course Info

Instructor: Mukto Akash
Office/Extension: MC 6508 x36655
Email: mukto.akash@uwaterloo.ca
Office Hours:
Tuesdays noon - 2pm
Thursdays 2 - 3pm
Textbook: Reading, Discovering, and Writing Proofs Version 0.5 (0.42-0.5 work)
Can be Acquired: at SCH as courseware

The content below is heavily influenced on the courseware.

Notes on Learn

The Course Notes are titled
– Reading, Discovering, and Writing Proofs

Statement:
If n is an integer, then \(n^2 ≥ n\).

Proof:
Since n is an integer, either n > 1, n = 0 or n < 0.
When n > 1, multiply both sides by n to get \(n^2 > n\).
When n = 0, we have \(n^2\) =0,so \(n^2 = n\).
Finally, when n < 0,we know that \(n^2 >0\), so \(n^2 > n\).
In all cases, n2 ≥ n is satisfied.

A statement is a sentence that has a definite state of being true or false.

ex. 2 + 2 = 4 (true)
3 + 2 < 5 (false)

not a statement: “Is 7 = 5?”

Definitions

Proposition: A mathematical claim that is posed in the form of a statement that needs to be proven true or demonstrated false by a valid argument.

Theorem: A particularly significant proposition.

Lemma: A proposition that is used to help prove the theorem.

Corollary: A proposition that follows a theorem.

Proposition 1:
For every real number x, \(x^2\) + 1 ≥ 2x

Proof: a series of convincing arguments that leaves no doubt that the stated proposition is true.

The Proof:
Suppose x is a real number.
Therefore, x - 1 must be a real number, and hence
\((x-1)^2\) ≥ 0
Expanding the terms on the left gives \(x^2\) - 2x + 1 ≥ 0. Adding 2x to both sides yields \(x^2\) + 1 ≥ 2x.

Axiom: A statement that is assumed to be true.

Flawed Proofs (some examples)

Identify the flaw in the proof
Statement: 1 = 2.
Proof: Let a=b
then \(a^2\) = ab
then \(a^2−b^2 = ab−b^2\)
then (a+b)(a−b) = b(a−b)
then a+b = b
then 2b = b
hence 2 = 1

In this case, (a-b) can be 0, and you cannot divide both sides by 0. The mistake happens on the third line.

Statement: 4 = 5
Proof Follow the steps
−20 = −20
16 − 36 = 25 − 35
\(4^2 −9*4=5^2 −9*5\\ 4^2−2*4*(\frac{9}{2})^2+ 2 = 5^2−2*5*\frac{9}{2}+\frac{9}{2}\\ (4−\frac{9}{2})^2 = (5-\frac{9}{2})^2\\ 4 - \frac{9}{2} = 5 - \frac{9}{2}\\ 4 = 5\)

In this case you cannot get rid of the exponents on both sides. The mistake happens on the fifth line.

Negation

Truth Table

The \(\land\) acts as “AND” and it is False when there is at least one False, and True otherwise.
The \(\lor\) acts as “OR” and it is True when there is at least one True, and False otherwise.

\(\lnot\) denotes a “NOT” sign

De Morgan’s Laws:

Law 1:

\(\lnot\) (\(\lnot\) A) = A

Law 2:

(\(\lnot\)A)∨(\(\lnot\)B) ≡ \(\lnot\)(A ∧ B)
(\(\lnot\)A)∧(\(\lnot\)B) ≡ \(\lnot\)(A ∨ B)

Law 3:

(A ∧ B) ∧ C ≡ A ∧ (B ∧ C)
(A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
associativity law

Proving Law 2

Start out with: \(\lnot\)((\(\lnot\)A)∧(\(\lnot\)B))
\(\lnot\)((\(\lnot\)A)∧(\(\lnot\)B)) ≡ (\(\lnot\)(\(\lnot\)A))∨(\(\lnot\)(\(\lnot\)B))
The (\(\lnot\)A)∧(\(\lnot\)B) undergoes negation
≡ (A) ∨ (B)
This yields just (A) ∨ (B)

Knowing Law 1
(\(\lnot\)A)∧(\(\lnot\)B) ≡ \(\lnot\)(\(\lnot\)(\(\lnot\)A)∧(\(\lnot\)B))) ≡ \(\lnot\)(A ∨ B)

By negating (A) ∨ (B), we can get: (\(\lnot\)A)∧(\(\lnot\)B) ≡ \(\lnot\)(A ∨ B)

Implication

Hypothesis: If … then

Conclusion: then…

If A, then B

Think of this like “If you give me $100, I will give you $200 tomorrow.” The implication is similar to if I keep my promise in this situation.

If the hypothesis is correct (I gave you $100 to begin with), then the implication is true if I give you back $200 tomorrow, or false I accept the money and do not give you back the money.

The hypothesis is false if you do not give me $100. I may give you $200 regardless tomorrow, making the implication true.

The hypothesis can also be false if you do not give me money, and I give you no money. In this case, the implication is also true.

Here are four implications. Only one is false. Identify the false implication.

1. If x is a real number and \(x^2\) < 0, then \(x^4\) ≥ 0.
2. If x is a real number and \(x^2\) < 0 then \(x^4\) < 0.
3. If n is a positive integer, then \(n^2\) +13 is not a perfect square.
4. If n is an integer and \(2^{2n}\) is an odd integer, then \(2^{−2n}\) is an odd integer.

Only the implication “If n is a positive integer, then \(n^2\) + 13 is not a perfect square.” is false.

Analysis of a Proof:

Divisibility of integers

An integer m divides an integer n, and we write m | n, when there exists an integer k so n = km.

If m | n, then we say that m is a divisor or a factor of n, and that n is a multiple of m or than n is divisible by m.

3 | 6 since 6 = 3 * 2. That is, there exists an integer k such that 6 = 3k.

For all integers a, a | 0 since 0 = 0 * a. This is true for a = 0 as well.

Transivity of Divisibility

Let a, b, and c be integers. If a | b and b | c, then a | c.

Proof:
Assume a | b and b | c.
Since a | b there exists an integer r so that ra = b.
Since b | c there exists an integer s so that sb = c.
Substituting ra for b in the previous equation, we get (sr)a = c.
Since sr is an integer, a |c.

##Divisibility of Integer Combinations (DIC)

Let a, b, and c be integers. If a | b and a | c, then for any integers x and y, a | (bx + cy)

Since we are proving an implication, not using it we assume the hypothesis is true to demonstrate the conclusion is true. This is called a Direct Proof.

Proof:
Assume a | b and a | c.
Since a | b there exists an integer m so that ma = b
Since a | c there exists an integer j so that ja = c
Let x and y be integers.
bx + cy = (ma)x + (ja)y = a (mx +jy)
Since mx + jy is an integer, it follows the definition of divisibility that a | (bx + cy)

##Proof of Bounds by Divisibility

###Bounds by Divisibility (BBD)

Let a and b be integers, If a | b and b \(\ne\) 0, then |a| \(\le\) |b|.

Proof:
Since a | b, there exists an integer k so that b = ka.
Since b \(\ne\) 0, k \(\ne\) 0 But if k \(\ne\) 0, |k| \(\ge\) 1
Hence |b| = |ka| = |k||a| \(\ge\) |a|
(You can multiply |k| \(\ge\) 1 by |a| to get |k||a| \(\ge\) |a|)

Corollary

Let a and b be integers. If a | b and b | a, then a = ± b.

Can we use Bounds by Divisibility (BBD) if we did not say a \(\ne\) 0 and b \(\ne\) 0

The answer to that is we must consider a,b = 0 as a special case, and use BBD for other cases.

Proof:

Case 1: Since 0 | 0 and 0 \(\nmid\) n for any non-zero integer n,
then when a = 0, b must be zero and vice versa

Case 2:
When a \(\ne\) 0, and b \(\ne\) 0
From a | b and b \(\ne\) 0, we can use BBD to get |a| \(\le\) |b|
From b | a and a \(\ne\) 0, we can use BBD to get |b| \(\le\) |a|
Hence |a| = |b|
Therefore a = ± b

Negating an Implication

A \(\Rightarrow\) B and \(\lnot\)A v B are the same

\(\lnot\)(A \(\Rightarrow\) B) \(\equiv\) \(\lnot\)((\(\lnot\)A) v B)
\(\equiv\) ((\(\lnot\)(\(\lnot\)A)) \(\land\) (\(\lnot\) B))
\(\equiv\) A \(\land\) (\(\lnot\) B)

In A then B Implication
A and not B Negated Implication

If a | b and b|c then a|c.
Negated Implication:
a | b and b | c and a \(\nmid\) c

If a | bc then a|b or a|c.
Negated Implication:
a | bc and a \(\nmid\) b and a \(\nmid\) c

If a | b and b \(\ne\) 0, then|a|≤|b|.
Negated Implication:
a | b and b \(\ne\) 0 and |a| > |b|

Divisibility of Integer Combinations.

“If m is an integer and 14 | m,
prove that 7 | 135m + 693”.
Note that 7 \(\nmid\) 135, so this is not a straight-forward result.

Recall previously: Proposition (Divisibility of Integer Combinations (DIC))
Let a, b and c be integers.
If a | b and a | c, then for any integers x and y, a | (bx + cy).

Proof: Assume 14 | m
Since 7 | 14, by Transivity of Divisibility 7 | m
m = 7k, for some integer k

Now 135m + 693 = 135(7k) + 7(99) = 7(135k + 99)
As 135k + 99 is an integer, 7 | (135m + 693)

Converse

Given an implication:

If A then B.

the converse of “If A then B” (A \(\Rightarrow\) B) is “If B then A” (B \(\Rightarrow\) A)

An implication and its converse are not logically related.

##Sets

Sets are collection of objects, called elements or members

∅ = { }. The empty-set has nothing in it.
{∅} has one element, namely the empty set, so
{∅} ≠ ∅.

\(\mathbb{R}\) is the set of real numbers. This is essentially the set that contains every possible number we have seen (unless you have seen complex numbers).

\(\mathbb{Q}\) is the set of rational numbers. These are numbers of the type 2, 1, 5 , 2, etc. The members are fractions, with numerator and denominator both being integers, and denominator cannot be zero.

\(\mathbb{Z}\) = {…,−3,−2,−1,0,1,2,3,…}, the set of integers (whole numbers)

\(\mathbb{N}\) = {1,2,3,…}, the set of natural numbers (positive integers). Note that in MATH 135, N starts at 1 and 0 ∉ N. This may be different that what you learn in CS.

Set Builder Notation

There are two different styles in writing sets in set builder notation.

Style 1

S = {x ∈ T : P(x)} or alternatively S = {x ∈ T | P(x)}.
Read as: x is in T such that P(x)is true.

P(x) is called the membership criteria.
P(x) is an example of an open sentence:
a mathematical sentence whose truth value depends on the value of x, e.g., \(x^2\) −1 = 0(only true when x = ± 1).

For an object n to be in S, both n ∈ T and P(n) must be true.
If n ∈ T or P(n) is false, then n ∉ S.

Example: {n ∈ \(\mathbb{N}\): n < 1000 ∧ 7|n}
The members are: 7, 14, 21, . . . , 994,
i.e., all positive integers less than 1000 that are divisible by 7.

Style 2

S = {f(x):x ∈ T, P(x)} or alternatively S = {f (x) | x ∈ T, P(x)}.
Read as: f (x) is in T such that x satisfies P(x).

T has been already defined, and P(x) is still called the membership criteria.

f(x) is an expression in x, e.g., \(x^2\) − 1.

Example

all points on a circle of radius 8 centred at the origin

Solution:
S = {(x, y) ∈ \(\mathbb{R}\) * \(\mathbb{R}\) : \(x^2\) + \(y^2\) = 64} or S = {(8cos\(\Theta\), 8sin\(\Theta\)) : \(\Theta\) ∈ \(\mathbb{R}\), 0 \(\le\) \(\Theta\) \(\le\) 2\(\pi\) }

Union

S ∪ T = {x | (x ∈ S ) ∨ (x ∈ T )}

Intersection

S ∩ T = {x | (x ∈ S) ∧ (x ∈ T)}

Set Difference

Set of all elements in S but not T.

S - T = {x | (x ∈ S) and ∉ T} = {x | (x ∈ S) ∧ (x ∉ T)}

Complement

_
S = {x | x ∉ S}

CartesianProduct

S × T ={ (x,y) |x ∈ S,y ∈ T}

What common sets do the following sets refer to?
A {m ∈ \(\mathbb{Z}\):2|m} ∪ {2k + 1:k ∈ Z}
B {m ∈ \(\mathbb{Z}\):2|m} ∩ {2k + 1:k ∈ Z}

A This is the set of all integers

B This is an empty set

A set S is called a subset of a set T, written S ⊆ T, when the implication “if x ∈ S then x ∈ T” is true for every x in the universe of discourse.
To prove S ⊆ T , we prove the implication (x ∈ S) => (x ∈ T).

Prove:

{n ∈ \(\mathbb{N}\) : 5 | n + 2} ⊆ {2k + 1 : k ∈ \(\mathbb{N}\)}

when n = 8

8 ∈ {n ∈ \(\mathbb{N}\) : 5 | n + 2}

but 8 ∉ {2k + 1 : k ∈ \(\mathbb{N}\)}

Converse of DIC (Divisibility of Integer Combinations)

If for any integers x and y, a | (bx + cy)
Then a | b and a | c

Proof: Assume for any integer x,y a | (bx + cy)
then when x = 1, y = 0
a | (b(1) + c(0)), i.e. a | b
Use specific scenarios when it is true
then when x = 0, y = 1
a | (b(0) + c(1)), i.e. a | c

Converse in Sets

To prove S ⊆ T we prove the implication
x ∈ S and x ∈ T
Two sets S and T are equal i.e. S = T,
S and T have the same elements

[(x ∈ S) ∧ (x ∈ T) AND (x ∈ T) ∧ (x ∈ S)]

i.e. we prove
(1) S ⊆ T
(2) T ⊆ S

If and Only If

When A = B, A \(\leftrightarrow\) B is True.

Proof

If S = T, then S ∪ T and S ∩ T

(“\(\rightarrow\)”)

Assume S = T
Let x ∈ S ∩ T, then (x ∈ S) ∧ (x ∈ T)
Hence (x ∈ S) ∧ (x ∈ T)
Therefore (x ∈ S) v (x ∈ T)

Therefore x ∈ S ∪ T, so S ∩ T ⊆ S ∪ T
On the other hand, let y ∈ S ∪ T
Then (y ∈ S) v (y ∈ T)

At least one of y ∈ S or y ∈ T is a true statement. Without loss of generality (WLOG), assume y ∈ S
From assumption S = T, so when y ∈ S, then y ∈ T
Thus S ∪ T ⊆ S ∩ T

(“\(\leftarrow\)”)

S ∪ T = S ∩ T then S = T
Assume S ∪ T = S ∩ T
let (x ∈ S) then (x ∈ S) v (x ∈ T)
Thus x ∈ S ∪ T.
Since S ∪ T = S ∩ T, x ∈ S ∩ T
Hence (x ∈ S) ∧ (x ∈ T)
Thus x ∈ T. Therefore S ⊆ T
Similarly, T ⊆ S
Therefore S = T

Quantifiers

quantifier, variable, domain, open sentence

For all x ∈ \(\mathbb{R}\), \(x^2\) + 1 \(\ge\) 2x

Universal Quantifer: “For all”
Variable: x
Domain: “\(\mathbb{R}\)”
Open Sentence: \(x^2\) + 1 \(\ge\) 2x

For every natural number n, 2\(n^2\) + 11n + 15 is composite
Proof:
Let n ∈ \(\mathbb{N}\)
2\(n^2\) + 11n + 15 = (2n + 5)(n + 3)
Since n \(\ge\) 1, 2n + 5 \(\ge\) 2 and (n + 3) \(\ge\) 2
Also: n ∤ 3 \(\ne\) (2\(n^2\) + 11n + 15) as 2n + 5 \(\ne\) 1
as 2n + 5 ∈ \(\mathbb{Z}\), (n + 3) | (2\(n^2\) + 11n + 15)
So 2\(n^2\) + 11n + 15 is composite

\(\forall\) x ∈ \(\mathbb{Z}\), a | (bx + c)
Proof:

Pick x = 1
a | (b(1) + c)
a | b + c

In this case we use the substitution method

The Select Method

Used to Prove \(\forall\) x ∈ S, P(x):

Select a representative mathematical object x ∈ S. This cannot be a specific object. It has to be a placeholder, (a variable) that the argument would work for any specific member of S.

Then show that the open sentence P would work for any representative x.

For each x ∈ \(\mathbb{R}\), x < x + 1
Proof:
Let x be a real number.
Therefore (x + 1) - (x) = 1
Since (x + 1) - (x) > 0
x < x + 1 is true
Thus, by select method, x ∈ \(\mathbb{R}\), x < x + 1 is a true statement

For every natural number n, n \(\le\) \(n^2\)
Proof:
Let P(x): x \(\le\) \(n^2\). We know that the set of natural numbers is given by

\(\mathbb{N}\) = {1, 2, 3, 4, 5, …}

Let n ∈ \(\mathbb{N}\).
Since n is a natural number, n \(\ge\) 1 Multiply both sides of the inequality by n (note: n is positive) to generality

n * n \(\ge\) n * 1
\(n^2\) \(\ge\) n

Thus, P(n) is true. Therefore, by the select method, \(\forall\) n ∈ \(\mathbb{N}\), P(n) is a true statement.

Existential Quantifier

\(\exists\) x ∈ S, P(x)

Also means:

1. There is an x ∈ S such that P(x) is true
2. P(x) is true for some x ∈ S
3. At least one x ∈ S satisfies P(x)
4. S has an element x such that P(x) is satisfied

The Construct Method

Used to prove \(\exists\) x ∈ S, P(x)

\(\exists\) x ∈ {1,2,3,4}, such that x is even

Proof:
Consider x = 2. Since 2 is an element of the given domain, and 2 is even, therefore the above statement is true.

Assuming a Quantified Statement is True

The Substitution Method

Used to prove \(\forall\) x ∈ S, P(x)

Substitute an appropriate value of x from S into the open sentence P, and use the fact that P(x) must be true to arrive at the desired conclusion.

If \(\forall\) x ∈ \(\mathbb{N}\), n | x then n = 1

The trick here is to use an appropriate value of x from \(\mathbb{N}\) that helps give the conclusion of n = 1.
Proof:
Assume \(\forall\) x ∈ \(\mathbb{N}\), n | x.
Since x ∈ \(\mathbb{N}\), consider x = 1. By our own assumption n | 1.
We know that the only positive divisor of 1 is 1 itself. Therefore n = 1.

The Object Method

Used to prove \(\exists\) x ∈ S, P(x), it true

Use a symbol such as s to denote an element of S for which P(x) is true. Since we do not know exactly which element of S satisfies P, we cannot assign a specific value to x. Instead we use x as a variable.

Let n be an integer. Prove the following statement about n:
If n is of the form 4l + 1 for some positive integer l, then 8 | (\(n^2\) -1)

\(\exists\) l ∈ \(\mathbb{Z}\), such that n = 4l + 1

Our goal is to prove 8 | (\(n^2\) - 1),
which is equivalent to proving that k ∈ \(\mathbb{Z}\), 8k = (\(n^2\) - 1)

Proof: Assume, by the object method, that we can write n = 4l + 1 for some integer l.
let k = \(2l^2\) + l. Since l is an integer, therefore k must be also an integer.
In that case, \(n^2\) - 1 = \((4l + 1)^2\) - 1 = \(16l^2\) + 8l + 1 - 1
\(16l^2\) + 8l = 8(\(2l^2\) + l) = 8k

Thus according to the construct method, we have shown that k ∈ \(\mathbb{Z}\), 8k = (\(n^2\) - 1)
Therefore 8 | (\(n^2\) -1)

Contrapositive

\(\not\)B \(\rightarrow\) \(\not\)A \(\equiv\) A \(\rightarrow\) B

When to use Contrapositive:

• when the statement Not A or Not B gives useful information
• if A or B have conditions that are only one of two possibilities (ex. odd or even)

Proof by Contradiction

A ∧ \(\not\)A must be false. “A ∧ \(\not\)A must be true” is a Contradiction

When to use Contradiction:

• when it is difficult to use direct method
• when NOT B gives more useful information than B

One-to-One: x has only one y value

Surjection/Onto: y has only one x value

A function f : S → T that is both one-to-one and onto is said to be a bijection

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

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

• 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 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).