GCD-LCM

Save all functions into the same file named gcdlcm.py.

1. Write the funcion gcd() that takes two positive integers a and b, and returns its greatest common divisor. Proposed method: using the following sequence min(a,b), min(a,b)-1, …, 2, 1, the first element of this sequence that divides both a and b is its greatest common divisor. Examples:

   >>> gcd (15,25)
   5
   >>> gcd (36, 90)
   18
   >>> gcd(453, 87)
   3
   >>> gcd(462, 1071)
   21
   

   Note

   More tests are provided in file gcd-1.txt

2. Write the function gcd_euclides_1() that takes two positive integers a and b, and returns its greatest common divisor. Use the Euclides method based on the following gcd properties:

   • \(gcd(a,b)=gcd(b,a)\)

   • if \(a>b\) then \(gcd(a,b)=gcd(a-b,b)\)

   • if \(b>a\) then \(gcd(a,b)=gcd(a,b-a)\)

   • \(gcd(a,a)=a\)

   Examples: \(gcd(5,15)=gcd(5,10)=gcd(5,5)=5\)

   >>> gcd_euclides_1 (15,25)
   5
   >>> gcd_euclides_1 (36, 90)
   18
   >>> gcd_euclides_1 (453, 87)
   3
   >>> gcd_euclides_1 (462, 1071)
   21
   

   Note

   More tests are provided in file gcd-2.txt

3. Write the function gcd_euclides_2() that takes two positive integers a and b, and returns its greatest common divisor. Use the Euclides method based on the following gcd properties:

   • if \(a=c\times b+r\), then \(gcd(a,b)=gcd(b,r)\)

   • \(gcd(a, 0)= a\)

   Examples: \(gcd(567,28)=gcd(28,7)=gcd(7,0)=7\)

   >>> gcd_euclides_2 (15,25)
   5
   >>> gcd_euclides_2 (36, 90)
   18
   >>> gcd_euclides_2 (453, 87)
   3
   >>> gcd_euclides_2 (462, 1071)
   21
   

   Note

   More tests are provided in file gcd-3.txt

4. Write the function lcm() that takes two positive integers a and b, and returns its least common multiple . Use some of the previous functions. Examples:

   >>> lcm (15,25)
   75
   >>> lcm (36, 90)
   180
   >>> lcm (453, 87)
   13137
   >>> lcm (462, 1071)
   23562
   

   Note

   More tests are provided in file lcm.txt

Solution

A solution of these functions is provided in the gcdlcm.py file.