Number Theory

Question 1

How do you implement the Euclidean Algorithm? What is it used for?

Answer 1

The Euclidean algorithm is used to determine the GCD of two numbers (a, b).

You start off with a divide between two columns labeled a|q. Under ‘a’ you place the largest of the two numbers and then under that, the smallest number. You treat these as the first two remainders. Next on the second row of the second column(q), you write how many times number 2(b) goes into number 1(a), then you write the remainder in column (a). You keep repeating this until you can evenly divide the remainder column and have a remainder of zero, the last remainder is the GCD of the two integers and is written:

GCD(a, b) = (final-remainder)

Question 2

How do we determine the GCD using prime factorisation?

Answer 2

We write our two integers in two seperate tables, and on the right column of each we start with two, and calculate how many times it divides our integer evenly, then write that divisibility under the original number, we then check if it is divisible by 2, if not, we move onto the next prime, and the next, and then the next until it is fully factorised. We do this for both, and then write out the prime factors as (P(1)^n x P(2)^n x …..) where P is the prime number and n is how many times it is a factor.

We then use the formulae of (P(1)^min{a, b} * P(2)^min{a, b} * P …..) until all factors are used, to determine the GCD. We denote min, as to chose the smallest power of the two prime factors.

Question 3

How do we determine LCM using prime factorisation?

Answer 3

We write our two integers in two seperate tables, and on the right column of each we start with two, and calculate how many times it divides our integer evenly, then write that divisibility under the original number, we then check if it is divisible by 2, if not, we move onto the next prime, and the next, and then the next until it is fully factorised. We do this for both, and then write out the prime factors as (P(1)^n x P(2)^n x …..) where P is the prime number and n is how many times it is a factor.

We then use the form (P(1)^max{a, b} * P(2)^max{a, b} * P…..), for all factors, using the greater of the two powers for all prime factors, to determine the LCM.

Question 4

Define “Relatively Prime.”

Answer 4

Relatively prime is where the GCD of two numbers is “1”, meaning they are relatively prime.

Question 5

What is meant by multiplicitive inverse?

Answer 5

Multiplicitive inverse takes the form

x*y == 1(mod n)

We say x and y are the multiplicitive inverse’s of one another when they yield the remainder 1.

Question 6

How is a|b read?

Answer 6

“a ‘divides’ b”