4.2 Primes and GCD

Question 1

Definition of prime

Answer 1

An integer p greater than 1 is called prime iff the only positive factors of p are 1 and itself

Question 2

How to show if an integer is prime

Answer 2

If n is a composite ionteger( not prime) then it has a prime divisor less than or equal to the square root of n

Question 3

Steps to find the prime factorization of a number

Answer 3

1. Divide the number by successive primes starting with the smallest prime, 2.
2. Continue factoring till you reach a prime number
3. The prime factorization is the multiplication of all the primes

Question 4

How to find the greatest common divisor of two numbers

Answer 4

By using the prime factorization, and take the min exponential of all primes in both numbers

Question 5

How to find the least common multiple of two numbers

Answer 5

By using the prime factorization, and take the max exponential of all primes in both numbers