Factors

If a is a factor of b, we also say:

• b is a multiple of a
• a is a divisor of b
• a divides b
• b is divisible by a

Properties of divisibility

• if a

  b and a

  c then a

  b + c and a

  b – c

• if a

  b and a

  c then a

  sb + tc

• if a

  b and b

  c then a

  c

Prime numbers

If p is prime, and p = ab, then either a = 1 or b = 1.

Fundamental theorem of arithmetic

A composite positive integer can be factorised as a product primes. Further, a given integer has only one such factorisation.

e.g. 14175 = 3⁴ × 5² × 7

Testing for primes

Three ways of expressing the same idea

• If n is composite, then n has a factor c such that 1 < c ≤ sqrt(n)
• Any composite number n has a prime factor ≤ sqrt(n)
• Let n be a positive integer greater than 1. If n has no prime factor ≤ sqrt(n), then n is prime.

Greatest common divisor

Let a, b ∈ ℤ. Any integer d such that d | a and d | b is called a common divisor or common factor of a and b. The largest d is the greatest common divisor, written as gcd(a, b)

Least common multiple

Any m > 0 such that a | m and b | m is a common multiple of a and b. The smallest common multiple is written lcm(a, b)

Coprime, relatively prime

If the gcd of a and b is 1 then we say that a and b are coprime or relatively prime.

Applying fundamental theorem of arithmetic

To find the gcd of two numbers 14175 and 16758, we multiply all of the common prime factors of both.

14175 = 3⁴ × 5² × 7

16758 = 2 × 3² × 7² × 19

gcd(14175, 16758) = 3² × 7

To find the lcm of two numbers 14175 and 16758 we need the smallest product of prime factors that include everything in both numbers.

e.g. lcm(14175, 16758) = 2 × 3⁴ × 5² × 7² × 19 = 3770550

• if a, b > 0 then gcd(a, b) × lcm(a, b) = ab

The Euclidean algorithm

Let a and b be positive integers. Suppose that

a = q₁b + r₁

b = q₂r₁ + r₂

r₁ = q₃r₂ + r₃

…

r_{n – 2} = q_nr_{n – 1} + r_n

r_{n – 1} = q_{n + 1}r_n

Then gcd(a, b) = r_n

• Note the down and to the left movement of each part.
• r_n is the last non-zero remainder.

e.g. Find the gcd of 854 and 651.

854 = 1 × 651 + 203

651 = 3 × 203 + 42

203 = 4 × 42 + 35

42 = 1 × 35 + 7

35 = 5 × 7

So gcd(854, 651) = 7

Solving equations like ax + by = c (Bezout property)

Consider ax + by = c

• if c = gcd(a, b) then it has a solution
• if c is a multiple of gcd(a, b) then it has multiple solutions
• if c is not a multiple of gcd(a, b) then there are no solutions

e.g. Find a solution for 30x + 73y = 1

Compute gcd(73, 30)

73 = 2 × 30 + 13 30 = 2 × 13 + 4 13 = 3 × 4 + 1

so 1 is the gcd.

Reversing this,

1 = 13 – 12

= 13 – (3 × 4)

= 13 – 3 × (4)

= 13 – 3 × (30 – 2 × 13)

= 13 - 3 × 30 + 6 × 13

= –3 × 30 + 7 × 13

= –3 × 30 + 7 × (73 – 2 × 30)

= –3 × 30 + 7 × 73 - 14 × 30

= –17 × 30 + 7 × 73

Therefore x = –17, y = 7

Modulo

If m | a – b, then a and b are congruent modulo m

a ≅ b mod(m)

which can also be written as

• m

  a – b

• a = b + km, k ∈ ℤ
• a and b have the same remainder when divided by m

Properties

If a ≅ b(mod m) and c ≅ d(mod m) (i.e. they have the same mods)

• a + c ≅ b + d(mod m)
• a – c ≅ b – d(mod m)
• ac ≅ bd(mod m)
• ca ≅ cb (mod m)
• aⁿ ≅ bⁿ(mod m)

• if a ≅ b(mod m) and n

  m then a ≅ b(mod n)

Simplifying modulo

e.g. Simplify 10^123456789 modulo 41

1. Start by trying things out, we want to find a 1. 10² = 100 ≅ 18(mod 41)

   10³ ≅ 180 ≅ 16(mod 41)

   10⁴ ≅ 160 ≅ –4(mod 41)

   10⁵ ≅ -40 ≅ 1(mod 41)

2. Now that we have a 1, try to rewrite the equation to use that to simplify

10^123456789 = 10^123456785 × 10⁴

≅ 10^{5q + 4} ≅ 10^5q + 10⁴ (mod 41) ≅ 1^q × (–4) (mod 41) ≅ –4(mod 41) ≅ 37(mod 41)

Solving congruence

We can use congruences to solve equations and vice versa.

79x ≅ 5347(mod 45) is the same as 79x – 45y = 5347

Then we apply the same steps as above.

1. Apply the Euclidean algorithm
2. Reverse the process to obtain a Bezout identity
3. Determine the solution(s)

Number of solutions

Consider ax ≅ b(mod m)

• if a and m are coprime then the congruence has a unique solution
• if gcd(a, m) isn’t a factor of b then there is no solution
• if gcd(a, m) is a factor of b then the congruence has a unique solution mod m
• if g = gcd(a, m) is a factor of b then the congruence has g different solutions mod m

Relations

See course notes for introduction, definitions.

Reflexive

A relation is reflexive if for every a ∈ A it is true that a R a

i.e. if every element is related to itself.

How to prove

“Let x ∈ S. Then … and thus x ~ x”

Symmetric

A relation is symmetric when for all a, b in A, if a R b then b R a

i.e. if a R b then b R a.

How to prove

It’s an “if then” proof, so we start by assuming that it is true (a R b), and then prove that b R a.

“Let x, y ∈ ℝ and assume x ~ y … “ then prove y ~ x

Transitive

R is transitive if a R b and b R a then a R c

i.e. if a is related to b, and b is related to c, then a is related to c.

How to prove

Also an “if then” proof, this time involving three variables.

“Let x, y, z ∈ ℝ and assume x ~ y and y ~ z then …”

Antisymmetric

R is antisymmetric if a R b and b R a then a = b

i.e. two different elements of A may be related by R one way around, or the other, or neither, but not both.

How to prove

As above, an “if then” proof

Equivalence relations

A relation that is reflexive, symmetric, and transitive.

roughly means “the same”.

Equivalence class

Let ~ be an equivalence relation on a set A. For any a ∈ A, the equivalence class of a with respect to ~ is the set [ a ] = { x ∈ A | x ~ a}

• every element is contained in its own equivalence class
• equivalence classes cannot be empty
• equivalence classes are sets: we prove they are equal by proving LHS ⊆ RHS and RHS ⊆ LHS

Partial order

A relation that is reflexive, anti-symmetric and transitive is called a partial order.

• tells us which of two elements “comes first”
• “poset” = partially ordered set

Hasse Diagram

• shows a partial order on a finite set
• if two sets S and T are related then we place S further down the page than T and draw a line between them
• don’t draw loops
• don’t draw lines that can be attained by transitivity

Definitions in relation to partial order

Maximal

If it is related to no element except itself, i.e. has nothing above it.

Greatest

If every element is related to it, i.e. it is ‘greater than’ or equal everything else.

• any greatest element is maximal
• there is only one greatest element (if any)
• if there is a unique maximal element, then it is greatest

Minimal

If no element except itself is related to it, i.e. has nothing below it.

Least

If it is related to every element, i.e. ‘less than’ or equal to everything

• any least element is minimal
• there is only one least element (if any)
• if there is a unique minimal element, then it is least

Low and upper bound for partial order

• most often asked to determine after sketching a Hasse diagram (which makes it easier)

The greatest lower bound of a and b is glb(a, b)

The least upper bound of a and b is lub(a, b)

(I rarely see them referred to as glb and lub, however.)