Question

use the euclidean algorithm to compute the greatest common divisor of 726 and 275 to express HCF (726,275) as a linear combination of 726 and 275

Answer 1

Euclid's algorithm:

Step 1. Divide the larger number by the smaller one: 
726 ÷ 275 = 2 + 176;

Step 2. Divide the smaller number by the above operation's remainder: 
275 ÷ 176 = 1 + 99;Step 3. Divide the remainder from the step 1 by the remainder from the step 2: 
176 ÷ 99 = 1 + 77;Step 4. Divide the remainder from the step 2 by the remainder from the step 3: 
99 ÷ 77 = 1 + 22;Step 5. Divide the remainder from the step 3 by the remainder from the step 4: 
77 ÷ 22 = 3 + 11;Step 6. Divide the remainder from the step 4 by the remainder from the step 5: 
22 ÷ 11 = 2 + 0;At this step, the remainder is zero, so we stop: 
11 is the number we were looking for, the last remainder that is not zero. 
This is the greatest common factor (divisor).

Greatest (highest) common factor (divisor)
gcf, gcd (726; 275) = 11;

Final answer: 
Greatest (highest) common factor (divisor) 
gcf, gcd (726; 275) = 11; 
Numbers have common prime factors.

Calculator: greatest common factor (divisor) gcf, gcd

Integer number 1:Integer number 2:

Latest calculated greatest common factors (divisors), gcf, gcd

gcf, gcd (42; 118) = 2Oct 01 16:08 UTC (GMT)gcf, gcd (1,024; 195) = 1; 
coprime numbers (relatively prime)Oct 01 16:08 UTC (GMT)gcf, gcd (250; 125) = 125 = 53Oct 01 16:08 UTC (GMT)gcf, gcd (726; 275) = 11Oct 01 16:08 UTC (GMT)gcf, gcd (15; 8) = 1; 
coprime numbers (relatively prime)Oct 01 16:08 UTC (GMT)gcf, gcd (33; 110) = 11Oct 01 16:08 UTC (GMT)gcf, gcd (650; 2,600) = 650 = 2 × 52 × 13Oct 01 16:08 UTC (GMT)gcf, gcd (14; 18) = 2Oct 01 16:08 UTC (GMT)gcf, gcd (48; 136) = 8 = 23Oct 01 16:08 UTC (GMT)gcf, gcd (7; 13) = 1; 
coprime numbers (relatively prime)Oct 01 16:08 UTC (GMT)gcf, gcd (445; 336) = 1; 
coprime numbers (relatively prime)Oct 01 16:08 UTC (GMT)gcf, gcd (168; 189) = 21 = 3 × 7Oct 01 16:08 UTC (GMT)gcf, gcd (73; 73) = 73Oct 01 16:08 UTC (GMT)gcf, gcd, see more...

Tutoring: what is it and how to calculate the greatest common factor GCF of integers numbers (also called greatest common divisor GCD, or highest common factor, HCF)

If "t" is a factor (divisor) of "a" then among the prime factors of the prime factorization of "t" will appear only prime factors that also appear in the prime factorization of "a", and the maximum of their exponents is at most equal to those involved in the prime factorization of "a".

For example, 12 is a divisor of 60:

12 = 2 × 2 × 3 = 22 × 3

60 = 2 × 2 × 3 × 5 = 22 × 3 × 5

If "t" is a common factor of "a" and "b", then the prime factorization of "t" contains only prime factors involved in the prime factorizations of both "a" and "b", by the lower powers (exponents).

For example, 12 is the common factor of 48 and 360.

12 = 22 × 3

48 = 24 × 3

360 = 23 × 32 × 5

Please note that 48 and 360 have more factors (divisors): 2, 3, 4, 6, 8, 12, 24. Among them, 24 is the greatest common factor, GCF (or the greatest common divisor, GCD, or the highest common factor, HCF) of 48 and 360.

The greatest common factor, GCF, is the product of all the prime factors involved in both the prime factorizations of "a" and "b", by the lowest powers.

Based on this rule it is calculated the greatest common factor, GCF, (or greatest common divisor GCD, HCF) of several numbers, as shown in the example below:

1,260 = 22 × 32

3,024 = 24 × 32 × 7

5,544 = 23 × 32 × 7 × 11

Common prime factors are: 2, its lowest power is min. (2; 3; 4) = 2; 3, its lowest power is min. (2; 2; 2) = 2;

GCF (1,260; 3,024; 5,544) = 22 × 32 = 252

If two numbers "a" and "b" have no other common factors (denominators) than one, gfc, gcd, hcf (a; b) = 1, then the numbers "a" and "b" are called COPRIME, or prime to each other.

If "a" and "b" are not coprime, then every common factor of "a" and "b" is a also a factor (divisor) of the greatest common factor, GCF (greatest common divisor, GCD, highest common factor, HCF) of "a" and "b".