# CMPUT272 Lecture Notes - Lecture 13: Maltese Lira, Linear Combination, Becquerel

For unlimited access to Class Notes, a Class+ subscription is required.

October 21 2014

ETLC 2-001

Definitions

Divides:

m,n such that m ≠ 0, (m|n) ( q ,n=qm)∀ ∈ℤ ∃ ∈ℤ⟺

(m divides n if and only if there is a q such that q*m = n)

GCD:

x,y such that x ≠ 0 y ≠ 0, ∀ ∈ℤ ∨

z z = gcd(x,y) z|x z|y ( w such that w|x w|y, w ≤ z)∀ ∈ℤ ∧ ∧ ∀ ∈ℤ ∧⟺

(z divides x and y, and any other number that divides x and y is less than z)

Q.R Theorem

x , b +, !q,r ( x = bq+r 0≤r≤b )∀ ∈ℤ ∀ ∈ℤ ∃ ∧

Properties of Integers: Number Theory

Theorem:

m,n +, m|n m ≤ n∀ ∈ℤ ⟹

Proof:

Let m,n Z+∈

Assume m|n,

then n = qm for some q Z+∈

Suppose n < m

then qn < qm

Since n ≤ qn, this give n < qm

"n < qm" contradicts "n = qm"

n ≥ m∴

(by hypothetical reasoning, and universal generalization)

Theorem:

The greatest common divisor of m and n is a linear combination,

with linear coefficiants, of m and n.

m,n , a,b∀ ∈ℕ ∃ ∈ℤ ,m≠0 n≠0, gcd(m,n) = am + bn∨

Example:

m=24, n=20

gcd(24,20)=4

Candidates for am+bn:

a b am+bn

0 0 0

0 1 20

1 0 24

1 1 44

0 -1 -20

-1 -1 -44

1 -1 4