0
There are two main methods:
- Euclid's method
- Choose one of the numbers to be the dividend of a division and the other to be the divisor.
- Perform the division
- Ignore the quotient and keep the remainder
- If the remainder is zero, the last divisor is the GCD
- Replace the dividend by the divisor
- Replace the divisor by the last remainder
- Repeat from step 2.
- Prime factorisation
Multiply the common primes to their lowest power together to get the GCD.
The first is limited to two numbers, but the latter can be used to find the gcd of any number of numbers.
Examples:
GCD of 500 and 240:
- Euclid's method:
240 ÷ 20 = 6 r 0
gcd = 20
- Prime factorisation:
240 = 24 x 3 x 5
gcd = 22 x 5 = 20
Still curious? Ask our experts.
Chat with our AI personalities
Professor
Lao
RafaAdd your answer:
Earn +20 pts
What is Euclid's Algorithm?
Euclid's algorithm is a popular algorithm to compute the GCD of two numbers. Algorithm: Gcd(a,b) = Gcd(b, a mod b), where a>=b and Gcd(a,0) = a Say we want to find the GCD of 72 and 105. 105 mod 72 = 33, so GCD(72,105) = GCD(33,72) 72 mod 33 = 6, so GCD(33,72) = GCD(6,33) 33 mod 6 = 3 so GCD(6,33) = GCD(3,6) 6 mod 3 = 0 so GCD(3,6) = GCD(0,3) = 3. So the GCD of 72 and 105 is 3.
Find the greatest common divisor in of 11 plus 7i and 18-i?
Use the division algorithm. If b = pa + r, then gcd(b,a) = gcd(a,r). Then you can apply the division algorithm again with a = qr + r' and gcd(a,r) = gcd(r, r'). Note that each time the square norm of the remainder gets smaller and smaller, so eventually this process will terminate and you can get the answer. Here, it should be 1.
What is the largest number that can divide 121 and 143 without any remainders?
17,303
What number can be divided into both 35 and 56?
The number that can be divided into both 35 and 56 is the greatest common divisor (GCD) of the two numbers. To find the GCD, you can use the Euclidean algorithm, which involves dividing the larger number by the smaller number and then using the remainder as the new divisor. Repeating this process will eventually lead to a common divisor. In this case, the GCD of 35 and 56 is 7.
What is the GCD of 375 and 225?
GCD: 75
