Use the Euclidean algorithm to determine whether or not the

Use the Euclidean algorithm to determine whether or not the years 1812 and 2013 are relatively prime. Let k, m, n, Z^+ where k and m are relatively prime. Prove that if k|mn then k|n .

Solution

1) Two numbers are said to be relatively prme if their greatest common divisor is 1 which means no number bigger than 1 divides a and b, no prime number divides a and b and there should be no prime number that appears in prime factorisation of both a and b(here a and b are two numbers).

The Euclidean algorithm uses division algorithm iteratively which says , if d is a common divison of b and r, then since a= qr+b we have d as common divisor of a as well.

Let us see for given nmbers 1812, 2013

2013 = 1.1812+ 201
1812 = 9*201 + 3
201 = 3*67+0

Now here we got 0 as remainder that means there are prime numbers(here 3) which can divide and b

Hence 1812 and 2013 are not relatively prime