multiply A by a simple factor n. Let q be the next quotient
and E the remainder. Finally, divide D by E; let r be the
quotient, and suppose that there is no remainder. Then
E will be the H. C. F. required.
The work will stand thus :
A)B(p pA m)C D)nA(q qD E)D(r rE
First, to show that E is a common factor of A and B.
By examining the steps of the work, it is clear that E divides D, therefore also qD ; therefore qD + E, therefore mA ; therefore A, since m is a simple factor.
Again E divides D, therefore mD, that is, C. And since E divides A and C, it also divides pA + C, that is, B. Hence E divides both A and B.
Secondly, to show that E is the highest common factor.
If not, let there be a factor X of higher dimensions than E.
Then X divides A and B, therefore B - pA, that is, C ; therefore D (since m is a simple factor) ; therefore nA - qD, that is, E.
Thus X divides E ; which is impossible, since by hypothesis, X is of higher dimensions than E.
Therefore E is the highest common factor.
124. The highest common factor of three expressions A, B, C may be obtained as follows :
First determine F the highest common factor of A and B ; next find G the highest common factor of F and C ; then G will be the required highest common factor of A, B, 0.
For F contains every factor which is common to A and B, and G is the highest common factor of F and C. Therefore G is the highest common factor of A, B, C.
