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

43 views3 pages

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
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class