2.1 Prime Numbers and Factorisation Flashcards
How can we prove that a is a factor of b
If an integer k exists where b = k * a
Define what h is when h = hcf(a,b) and explain what it mean
h is highest common factor of a and b.
This means h is a factor of both a and b, also anything that is a factor of both a and b is also a factor of h.
What is the hcf(8,12)
4 and -4
Do the base case step
Do the induction step
Difference between mathematical induction and strong induction
In mathematical induction, you are only allowed to assume that P(k) is true. In strong induction you are allowed to assume that P(1), … , P(k) are all true. In other words, you are allowed to make more assumptions when using strong induction.
Use strong induction to explain/prove that every integer n>= 2 can be written as a product of prime numbers
Base case: P(2) is true
P(k+1) must be true whenever P(2), P(3), … ,P(k) are all true
The integer k + 1 can written as a product of primes and we can ssume that P(j) is true for all 2 <= j <= k
k+1 is either a prime number or it isn’t.
If it is: it can be written as a product of one prime number so there’s notjing more to prove
If it isn’t: we can write k + 1 = a * b where 2 <= a,b <= k.
We are therefore allowed to assume that P(a) and P(b) are both true. Since k+ 1 = a * b, therefore P(k+1) is true as well.
What is the fundamental theorem of arithmetic
Every integer n >= 2 can be written as a product of prime number. And this factorisation is unique (the same sets of prime numbers).
What is the division algorithm
If you divide a by b where b != 0. Then there is a unique quotient q and remainder r such that a = qb + r and
0 <= r <= |b|
