Divisibility And Euclid’s Algorithm Flashcards
What is definition 2.1?
d is a divisor of the integer a if and only if there is a unique integer b such that db=a.
What is a common divisor?
d is a common divisor if d|a and d|b
What is the greatest common divisor?
It is the unique integer d that satisfies
1. d|a and d|b
2. If c|a and c|b then c <= d (no common divisor is greater then d)
What is lemma 2.4 (cancellation lemma)?
If m,n,p are integers with m.p = n.p then either p = 0 or m = n
What is lemma 2.5?
Let a,b and c be integers
1. If a|b and b|c then a|c
2. If a|b and c|d then ac|bd
3. If m doesn’t equal 0, then a|b if and only if ma|mb
4. If d|a and a doesn’t equal 0, then |d| <= |a|
What is theorem 2.6?
Let a1,…,ak , u1,…,uk, a, b, c be integers
1. If c divides a1,…,ak, then c divides any linear combination of the integers a1,…,ak
2. a|b and b|a if and only if a = +- b
What is corollary 2.7?
If c divides a and b, then c divides au + bv for all integers u and v
What is lemma 2.8?
If a,b are integers with a = qb +r and 0<= r <b
Then gcd(a,b) = gcd(b,r)
What is theorem 2.9 (The remainder theorem)?
If a and b are integers with b>0, them there is a unique pair of integers a and r such that a = qb +r and 0<= r < b
What is theorem 2.16 (Bezout’s Identity)?
If a and b are integers (not both 0), then there exist integers u and v such that gcd(a,b) = au +bv
What is theorem 2.19 (Lamé’s theorem)?
The number of steps in the Euclidean algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers
What is theorem 2.21?
d = gcd(a,b)
An integer c has the form ax +by if and only if c is a multiple of d.
When are 2 integers coprime?
If the gcd = 1
What is corollary 2.23?
Two integers are coprime if and only if there exists integers x and y such that ax + by =1
What is corollary 2.24?
If gcd(a,b) = d then,
gcd(ma,mb) = md
For every integer m>0
gcd(u,v) = 1
Where u is the unique integer such that a =ud and v is the unique integer such that b = vd
