Number Theory and Notation Flashcards
a divides b
a | b
what will guarantee a number is a multiple of 3?
if a number is the product of 3 consecutive numbers, then that number is a multiple of 3.
GCD
greatest common divisor
Euclid’s Algorithm
a method of finding the GCD of two numbers. divide the larger number by the smaller number. if the remainder is 0, then the smaller number is the GCD. otherwise, let the smaller number become the largest number and let the remainder become the smallest number and repeat.
prime numbers
natural numbers greater than 1 whose only factors are 1 and itself
composite numbers
natural numbers greater than 1 that are not prime numbers
what is special about 1?
1 is neither prime nor composite
what does it mean for a and b to be relatively prime/coprime?
GCD(a,b) = 1
what is special about the GCD(a,b)?
the GCD(a,b) is the smallest value of c for which ax + by = c has integer solutions
what does it mean for GCD(a,b) = 1?
a and b are relatively prime/coprime
what is a diophantine equation?
an equation of the form ax + by = c where all the constants are integers and the only solutions of interest are integers
Euclid’s lemma
if p, a, b are integers and p is prime with p dividing ab, then p divides a or p divides b.
when does a general integer solution exist for ax + by = c?
when GCD(a, b) divides c
what does it mean when, given a diophantine equation, GCD(a,b) divides c?
there are infinitely many integer solutions
what does it mean when, given a diphantine equation, GCD(a,b) does not divide c?
there are no integer solutions
