Number Theory Flashcards
What is number theory useful for?
Cryptographic techniques. Finding large primes + nums with exactly 2 prime factors are key to most encryption techniques.
What makes a whole number prime?
If it’s at least 2 + no number greater than 1 + less than it divides evenly into it. We only need to test up to the square root of the number to discern whether it’s prime + we don’t need to test even numbers after 2. There is no largest prime number.
What is a non prime number known as?
A composite number. We write its prime factors in sequences.
What method allows us to find all prime numbers up to a certain number?
The Sieve of Eratosthenes. We write out numbers from 2 up to chosen number + strike out multiples of 2, then move on to next number not stricken out + do the same. We do this until there are no numbers left.
How do we find the prime factors of a composite number?
Composite nums can be written as product of 2 smaller numbers (factors). If either of these factors are composite, we can further factor it until eventually all factors are prime. We write each of these into a sequence. This is called prime factorisation.
What is the fundamental theorem of arithmetic?
It states that a whole num which is greater than 1 is either prime or can be written as a product of primes in only 1 way.
What is the greatest common divisor?
The largest whole number which divides evenly into other chosen nums. Its prime factors can be found by finding prime factors of 2 chosen nums + choosing factors which are in both lists. If same factor in both lists, use smaller num of copies. We multiply this list of factors together to find the GCD.
What is the lowest common multiple?
Lowest num which can be evenly divided into 2 numbers. First find prime factors of 2 nums + then choose factors which are in either list. If same factor in both, put in larger num of copies. Multiply this list of factors together to find LCM.
What is a divisor?
Divisor of a natural num is another natural num which divides evenly into it. 1 is divisor of any num + any num is divisor of itself. We can find all divisors of num by taking all combos of its prime factors. Using all prime factors gives us num + using none gives us 1.
What is a subsequence?
A new sequence found by choosing portion of existing sequence. e.g. [2,4,5] is subsequence of [1,2,4,5] but not of [1,2,3,4,5]. [] is subsequence of any sequence.
What is S {2,…3) if S = [2,4,6,8]?
[4,6]
What is S (2,…,1) if S = [2,4,6,8]?
[] If first num is higher than second, we return an empty sequence.
What is S(1,…,len(S))
S
