Matthew Palmer — Notes

Discrete Maths (MATH1081): Section 2 — Integers, Modular Arithmetic, and Relations

Factors

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

Properties of divisibility

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 = 34 × 52 × 7

Testing for primes

Three ways of expressing the same idea

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 = 34 × 52 × 7

16758 = 2 × 32 × 72 × 19

gcd(14175, 16758) = 32 × 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 × 34 × 52 × 72 × 19 = 3770550

The Euclidean algorithm

Let a and b be positive integers. Suppose that

a = q1b + r1

b = q2r1 + r2

r1 = q3r2 + r3

rn – 2 = qnrn – 1 + rn

rn – 1 = qn + 1rn

Then gcd(a, b) = rn

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

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 | ab, then a and b are congruent modulo m

a ≅ b mod(m)

which can also be written as

Properties

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

Simplifying modulo

e.g. Simplify 10123456789 modulo 41

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

    103 ≅ 180 ≅ 16(mod 41)

    104 ≅ 160 ≅ –4(mod 41)

    105 ≅ -40 ≅ 1(mod 41)

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

10123456789 = 10123456785 × 104

≅ 105q + 4 ≅ 105q + 104 (mod 41) ≅ 1q × (–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)

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}

Partial order

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

Hasse Diagram

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.

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

Low and upper bound for partial order

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