Elements of Algebra

CHAP. VII. OF ALGEBRA. 151 $a - nb$; therefore $d$ must also be the greatest common divisor of $a$ and $b$. 458. These things being laid down, let us divide, according to the rule, the greater number $a$ by the less $b$; and let us suppose the quotient to be $n$; then the remainder will be $a-nb$*, which must necessarily be less than $b$; and this remainder $a-nb$ having the same greatest common divisor with $b$, as the given numbers $a$ and $b$, we have only to repeat the division, dividing the preceding divisor $b$ by the remainder $a-nb$; and the new remainder which we obtain will still have, with the preceding divisor, the same greatest common divisor, and so on. 459. We proceed, in the same manner, till we arrive at a division without a remainder; that is, in which the remainder is nothing. Let therefore $p$ be the last divisor, contained exactly a certain number of times in its dividend; this dividend will evidently be divisible by $p$, and will have the form $mp$; so that the numbers $p$ and $mp$ are both divisible by $p$: and it is also evident that they have no greater common divisor, because no number can actually be divided by a number greater than itself; consequently, this last divisor is also the greatest common divisor of the given numbers $a$ and $b$. 460. We will now give another example of the same rule, requiring the greatest common divisor of the numbers $1728$ and $2304$. The operation is as follows: $1728) 2304 (1$ $1728$ --- $576)1728 (3$ $1728$ --- $0.$ Hence it follows that $576$ is the greatest common divisor, and that the relation $1728 : 2304$ is reduced to $3 : 4$; that is to say, $1728$ is to $2304$ in the same relation as $3$ is to $4$. * Thus, $b)a(n$, the supposed quotient. $nb$ --- $a-nb$