+
Related Flashcards
Cards In This Set
| Front | Back |
|
State the names of all 14 definitions / propositions from the GCD & Divisors unit
|
-Divisibility-TD: Transitivity of Divisibility-DIC: Divisibility of Integer Combinations-BBD: Bounds By Divisibility-DA: Division Algorithm-GCD: Greatest Common Divisor-GCD WR: Greatest Common Divisor With Remainder-EEA: Extended Euclidean Algorithm-GCD CT: Greatest Common Divisor Characterization Theorem-GCD OO: Greatest Common Divisor Of One-CAD: Coprimeness and Divisibility-DB GCD: Division By Greatest Common Divisor-LDET1: Linear Diophantine Equations Part 1-LDET2: Linear Diophantine Equations Part 2
|
|
State TD
|
Proposition: Let a, b, c Є Integers. If a | b and b | c , then a | c
|
|
State DIC
|
Proposition: Let a, b, and c be integers. If a|b and a|c,
then a|(bx+cy) for any x,y Є Integers
|
|
State BBD
|
Proposition: If a|b and b≠0, then |a| ≤ |b|
|
|
State the definition of Divisibility
|
Definition: An integer m divides an integer n, and we write m |n ,
if there exists an integer k so that n = km
|
|
State DA
|
Proposition: If a and b are integers, and b>0, then
there exist unique integers q and r such that a=qb+r where 0≤r<b
|
|
State GCD
|
Proposition: Let a and b be integers, not both 0. An integer d>0
is the greatest common divisor of a and b, written gcd(a,b) if and only if:
1) d|a
and d|b (Common) and2) if c|a and c|b, then c ≤ d (Greatest)
|
|
State GCD WR
|
Proposition: If a and b are integers not both 0, and q and
r are integers such that a = qb+r , then gcd(a,b) = gcd (b,r)
|
|
State EEA
|
Proposition: If d = gcd(a,b), then there exists integers
x,y such that ax+by=d
|
|
State GCD CT
|
Proposition: If d is a positive common divisor of the
integers a and b, and there exist integers x and y so ax+by = d, then d=gcd(a,b)
|
|
State GCD OO
|
Proposition: Let a and b be integers. Gcd( a,b) = 1 if and
only if there are integers x and y with ax + by = 1
|
|
State CAD
|
Proposition: If a, b and c are integers and c|ab and gcd(a,c)
= 1, then c|b
|
|
State DB GCD
|
Proposition: Let a,b be integers. If gcd(a,b) = d ≠ 0, then
gcd(a/d, b/d) = 1
|
|
State LDET1
|
Theorem:
Let gcd(a,b) = d. The linear Diophantine equation ax+by=c
has a solution if and only if d|c
|
|
State LDET2
|
(If you have solutions to the Linear Diophantine Equation
from LDET1, use this to find the complete set of solutions)
Theorem: Let gcd(a,b) = d ≠ 0.
If x = x0 and y = y0 is one particular integer
solution to the linear Diophantine equation ax+by=c, then the complete integer
solution is:
X= x0
+ (b/d)n , y = y0 – (a/d)n, ∀nЄ Integers
|
