MATH135

What is a prime number?

p ∈ ℕ and p > 1 and the only positive divisors of p are 1 and p.

What is gcd(a,b) by definition?

The greatest positive integer dividing both a and b.

What is Bézout’s Identity?

If d = gcd(a,b) then ∃s,t ∈ ℤ such that as + bt = d.

What is the divisor counting formula?

If n = p₁^α₁…pk^αk then the number of positive divisors is (α₁+1)…(α_k+1).

How do you prove A ⊆ B?

Let x ∈ A and show x ∈ B.

What must be shown to prove two sets A and B are equal?

Show A ⊆ B and B ⊆ A.

What is the base case in mathematical induction?

Verify P(A) where A is the starting integer.

What is the inductive step in standard induction?

Assume P(k) and prove P(k+1).

What is the inductive hypothesis in strong induction?

Assume P(A),…,P(k) and prove P(k+1).

State the gcd characterization theorem.

d = gcd(a,b) iff d ≥ 0 and d \| a and d \| b and ∃s,t ∈ ℤ such that as+bt=d.

What is the contrapositive of P ⇒ Q?

¬Q ⇒ ¬P.

State the Linear Diophantine Equation Theorem (LDET).

ax+by=c has an integer solution iff gcd(a,b) | c.

State Euclid’s Lemma.

∀a,b ∈ ℤ, ∀p ∈ P, if p | ab and p ∤ a then p | b.

Why is primality essential in Euclid’s Lemma?

Because if p is prime and p ∤ a then gcd(a,p)=1.

Why does the divisor formula multiply (α_i+1)?

Each divisor independently chooses an exponent between 0 and α_i for each prime.

When does {px+qy : x,y ∈ ℤ} equal ℤ for primes p,q?

If and only if p ≠ q.

Congruence addition rule

If a₁ ≡ b₁ (mod m) and a₂ ≡ b₂ (mod m), then a₁ + a₂ ≡ b₁ + b₂ (mod m).

Congruence multiplication rule

If a₁ ≡ b₁ (mod m) and a₂ ≡ b₂ (mod m), then a₁a₂ ≡ b₁b₂ (mod m).

What is a linear congruence?

A relation of the form ax ≡ c (mod m).

What is a solution to a linear congruence?

An integer x₀ such that ax₀ ≡ c (mod m).

When does ax ≡ c (mod m) have a solution?

It has a solution iff d | c where d = gcd(a,m).

What does a ≡ b (mod m) mean?

a ≡ b (mod m) means m | (a − b)

State Pascal’s Identity.

C(n,k)=C(n-1,k-1)+C(n-1,k).

What is the Binomial Theorem?

(x+y)^n = Σ from k=0 to n of C(n,k)x^{n-k}y^k.

What does it mean for ℚ to be dense in ℝ?

For all a,b ∈ ℝ with a<b there exists r ∈ ℚ such that a<r<b.

What does congruence mean?

Congruence is the relation ≡ defined by m \| (a − b).

When are two integers congruent modulo m in terms of remainders?

a ≡ b (mod m) iff a and b have the same remainder when divided by m.

Transitive property of congruence

If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).

Symmetric property of congruence

If a ≡ b (mod m), then b ≡ a (mod m).

What does a ≢ b (mod m) mean?

a ≢ b (mod m) means m ∤ (a − b).

Congruence power rule

If a ≡ b (mod m) then aⁿ ≡ bⁿ (mod m) for any positive integer n.

Congruence divide rule

If ac ≡ bc (mod m) and gcd(c,m) = 1, then a ≡ b (mod m).

Divisibility rule for 3

A number is divisible by 3 iff the sum of its digits is divisible by 3.

Divisibility rule for 11

A number is divisible by 11 iff Sₑ − Sₒ is divisible by 11 (Sₑ = sum of digits in even powers of 10, Sₒ = sum of digits in odd powers).

When dividing n by 3, what are the possible forms?

n=3k or n=3k+1 or n=3k+2 for some k ∈ ℤ.

Congruence class [a] mod m

The set [a] = {x ∈ ℤ : x ≡ a (mod m)}. There are exactly m distinct classes modulo m: [0], [1], ..., [m−1]. Example: for m=4, [2] = {..., −6, −2, 2, 6, 10, ...} = {4k+2 : k ∈ ℤ}

What is ℤₘ?

The set of m congruence classes: ℤₘ = {[0], [1], ..., [m−1]}. Addition: [a]+[b]=[a+b]. Multiplication: [a][b]=[ab]. Operations on ℤₘ are called modular arithmetic.

4 basic properties of ℤₘ

1) [a]+[0]=[a] (additive identity)
2) [a][0]=[0] (zero product)
3) [a]+[−a]=[0] (additive inverse)
4) [a][1]=[a] (multiplicative identity)

INV ℤₘ — When does [a] have a multiplicative inverse?

[a] in ℤₘ has a multiplicative inverse iff gcd(a,m)=1. When gcd(a,m)=1, the inverse is unique. (where 1 ≤ a ≤ m−1)

INV ℤₚ — Inverses in ℤₚ

For all prime p and every non-zero element [a] in ℤₚ, the multiplicative inverse [a]⁻¹ exists and is unique.

How do you find [a]⁻¹ in ℤₘ?

Solve [a][x]=[1], i.e. ax ≡ 1 (mod m). Rewrite as the linear Diophantine equation ax + my = 1, then solve using the Extended Euclidean Algorithm (EEA). The x-value gives [a]⁻¹.

Fermat's Little Theorem formula for [a]⁻¹

When p is prime and [a] is non-zero in ℤₚ: [a]⁻¹ = [a^(p−2)]. This is because Fermat's Little Theorem gives [a][a]^(p−2) = [1] in ℤₚ.

Corollary 8.7.2

For all prime p and all integers a: a^p ≡ a (mod p)

Splitting Modulus Theorem (SMT)

For integers a, m₁, m₂ with gcd(m₁,m₂)=1: the system n≡a (mod m₁) and n≡a (mod m₂) has exactly the same solutions as n≡a (mod m₁m₂).

Chinese Remainder Theorem (CRT)

For gcd(m₁,m₂)=1, the system n≡a₁ (mod m₁) and n≡a₂ (mod m₂) has a unique solution modulo m₁m₂. If n=n₀ is one solution, all solutions are n≡n₀ (mod m₁m₂).