Instruction
1
The greatest common divisor (GCD) of two integers is the largest integer that divided both the original numbers without a remainder. At least one of them must be different from zero, and the GCD.
2
The GCD is easy to calculate the Euclidean algorithm or the binary method. The Euclidean algorithm determine the GCD of integers a and b, one of which is not zero, there is a sequence of numbers r_1 > r_2 > r_3 > ... > r_n, where the element r_1 is equal to the remainder from dividing the first number by the second. And other members of the sequence equals the remnants of the division predprinyavshego member for the previous and the penultimate element is divided into the past without a trace.
3
Mathematically the sequence can be represented as:
a = b*k_0 + r_1
b = r_1*k_1 + r_2
r_1 = r_2*k_2 + r_3
...
r_(n - 1) = r_n*k_n,
where k_i is an integer multiplier.
GCD (a, b) = r_n.
4
The Euclidean algorithm called mutual subtraction, since the GCD is obtained by successive subtraction of the smaller from the larger. It is easy to assume that GCD (a, b) = GCD (b, r).
5
Example.
Find GCD (36, 120). The Euclidean algorithm subtract 120, the number that is a multiple of 36, in this case 120 – 36*3 = 12. Now subtract 120, the number of multiples of 12, will 120 – 12*10 = 0. Therefore, GCD (36, 120) = 12.
6
Binary the algorithm for finding the GCD is based on the theory of shift. According to this method the GCD of two numbers has the following properties:
GCD (a, b) = 2*GCD (a/2, b/2) for odd a and b
GCD (a, b) = GCD (a/2, b) for even a and odd b (the opposite is true GCD (a, b) = GCD (a, b/2))
GCD (a, b) = GCD ((a - b)/2, b) for odd a > b
GCD (a, b) = GCD ((b - a)/2, a) for odd b > a
Thus, GCD (36, 120) = 2*GCD (18, 60) = 4*GCD (9, 30) = 4* GCD (9, 15) = 4*GCD ((15 - 9)/2=3, 9) = 4*3 = 12.
7
Least common multiple (LCM) of two integers is the smallest integer that is a multiple of both original numbers without a remainder.
The NOC can be calculated using the GCD: NOC (a, b) = |a*b|/GCD (a, b).
8
The second method of calculating the knock – canonical decomposition of numbers into Prime factors:
a = r_1^k_1*...*r_n^k_n
b = r_1^m_1*...*r_n^m_n,
where the r_i are all Prime numbers and k_i and m_i are integers ≥ 0.
The NOC is represented in the form of the same Prime factors, where the degree is taken for the maximum of two numbers.
9
Example.
Find NOK (16, 20):
16 = 2^4*3^0*5^0
20 = 2^2*3^0*5^1
NOC (16, 20) = 2^4*3^0*5^1 = 16*5 = 80.