GCF Calculator with step by step solution using Euclidean Algorithm



Tutorial

The GCF(Greatest Common Factor),also known as the greatest Common Divisor,of two positive integers $a,b$, is the largest positive integer divides both $a$ and $b$.For instance, the GCF of $15$ and $35$ is $5$,since the positive factors of $15$ are $1,5,3,15$,positive factors of 35 are $1,7,5,35$.The positive integers divides both $15$ and $35$ are $1,5$, the largest of them is $5$.Of course, one can list all positive factors of integer $a$, and all positive factors of integer $b$, and hence find their largest common factor from these two list. However, this approach becomes impractical and time consuming when it comes to find GCF of two large number, say $6480$ and $8910$, since $6480$ has $50$ factors,$8910$ has $40$ factors,one has to find an alternative way of working out their GCF instead of trying to list all factors of both numbers. Euclidean Algorithm is one way of doing so.


First,Since $8910>6480$,we divide the large number 8910 by the small number 6480,we get:$$8910=6480\times1+2430$$ Next,we divide the divisor 6480 in the last step, by the reminder 2430,that is:$$6480=2430\times2+1620$$Next,we divide the divisor in the last step,2430,by the reminder 1620,that is:$$2430=1620\times1+810$$Similarly,we divide the divisor in the last step,1620,by the reminder 810,that is:$$1620=810\times2+0$$So,finally,we found $1620$ is divisible by $810$, hence the GCF of 8910 and 6480 is 810. In General,for two positive integers $a$ and $b$, say $a$ is the large one, to find their GCF, we perform the following: Divide $a$ by $b$,that is $$ a=b \times q_{1}+r_{1} $$ divide $b$ by $r_{1}$,$$ b=r_{1}\times q_{2}+r_{2}$$ divide $r_{1}$ by $r_{2}$, $$ r_{1}=r_{2} \times q_{3}+r_{3} $$ divide $r_{2}$ by $r_{3}$, $$ r_{2}=r_{3} \times q_{4}+r_{4} $$ divide $r_{3}$ by $r_{4} \cdots$, until we found the reminder is 0 or 1, if the reminder is 0, then the reminder from the second last step is the GCF, if the reminder is 1,then $a$ and $b$'s GCF is 1. You can try more examples on the calculator.