Number Theory Flashcards Preview

2. Fundamentals of Maths (CSC 1026) > Number Theory > Flashcards

Flashcards in Number Theory Deck (13)
Loading flashcards...
1

What is number theory useful for?

Cryptographic techniques. Finding large primes + nums with exactly 2 prime factors are key to most encryption techniques.

2

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.

3

What is a non prime number known as?

A composite number. We write its prime factors in sequences.

4

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.

5

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.

6

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.

7

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.

8

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.

9

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.

10

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.

11

What is S {2,...3) if S = [2,4,6,8]?

[4,6]

12

What is S (2,...,1) if S = [2,4,6,8]?

[] If first num is higher than second, we return an empty sequence.

13

What is S(1,...,len(S))

S