Week 3 - Properties of Integers, Primes, GCD & LCM Flashcards
What does the fundamental theorem of arithmetic state
Every integer n> 1 can be uniquely written as a product of prime integers
What is absolute number?
Written as |a| and can be thought of as the distance between a and 0 on the number line
What does the well-ordering principle state?
That it must have a minimum element, lower bound, etc.
What is the division algorithm?
a = bq + r, which obviously states r = a - bq
What is GCD?
d = gcd( a, b) if and only if d has the following two properties: (1) d divides both a and b. (2) If c divides both a and b, then c | d
What is LCM?
The lowest common multiple, a number that “a” and “b” both can divide into. lcm(a,b)= |a*b|/gcd(a,b)
What does relatively prime or coprime mean?
Two integers a and b are said to be relatively prime or coprime if gcd( a, b) = 1.
What does a is congruent to b modulo m mean?
Let m be a positive integer. We say that a is congruent to b modulo m. written a ≡ b (modulo m) or simply a ≡ b( mod m) if m divides the difference a –b. The integer m is called the modulus. The negation of a ≡ b( mod m) is written a ≡ b( mod m).
WLOG stands for?
WLOG stands for without loss of generality We can use it whenever our proof involves two or more sections that are identical except for a different choice being made.
Basically “I’ll show the proof for this one case, and the other cases are so similar that it would be a waste of time to write them out”
When is a set well-ordered?
A set S is well-ordered if every non-empty subset of S has a minimum member
How do you do a minimal counterexample proof?
cc. How to do a proof by minimum counterexample (Similar to proof by contradiction)
i. Suppose the claim is not true (Which means there must be a non-empty set of counterexamples)
ii. Let x be the minimum counterexample
iii. Prove that this leads to a contradiction
iv. Conclude that there is no minimum counterexample
v. Conclude that the set of counterexamples is empty
vi. Conclude that the claim is true!
What is Euclids algorithim based on?
i. GCD(a,b) = GCD(a-b, b)
ii. Corollary: GCD(a,b) = GCD (b, a mod b)
GCD(a,b)*LCM(a,b) = ?
|A*B|
