Elements of Algebra

CHAP. II. ADDITIONS. 497 wherefore $\frac{p}{q} - \frac{R}{s} = \pm \frac{1}{qs}$; and, since we suppose the doubtful sign to be taken conformably to that of the quantity $p-aq$, or $r$, the quantity $\frac{p}{q} - \frac{R}{s}$ must be positive, if $r$ be positive; and negative, if $r$ be negative: now, as $s < q$, and $R > P$ (hyp.), it is evident that $\frac{R}{s} > \frac{P}{q}$, (abstracting from the sign); therefore, the quantity $\frac{p}{q} - \frac{R}{s}$ will always have its sign different from that of $\frac{R}{s}$; that is to say, from that of $R$, since $s$ is positive; and, consequently, $p$ and $R$ will necessarily have different signs. This being laid down, we shall have, by substituting the above values of $y$ and $z$, $y - az = (p-aq)t + (r-as)u = rt + Ru$. Now $t$ and $u$ having different signs, as well as $p$ and $R$, it is evident, that $pt$ and $Ru$ will be quantities of like signs; therefore, since $t$ and $u$ are integer numbers, it is clear that the value of $y - az$ will always be greater than $r$; that is to say, than the value of $p-aq$, abstracting from the signs. But it remains to know whether, when the numbers $p$ and $q$ are given, we can always find numbers $r$ and $s$ less than those, and such that $ps-qr = \pm 1$, the doubtful signs being arbitrary; now, this follows evidently from the theory of continued fractions; but it may be demonstrated directly, and independently of that theory. For the difficulty is reduced to proving, that there necessarily exists an integer and positive number less than $p$, which being assumed for $r$, will make $qr \pm 1$ divisible by $p$. Now, suppose we successively substitute for $r$ the natural numbers $1, 2, 3$, &c. as far as $p$, and that we divide the numbers $q \pm 1, 2q \pm 1, 3q \pm 1$, &c. $pq \pm 1$ by $p$, we shall then have $p$ remainders less than $p$, which will necessarily be all different from one another; since, for example, if $mq \pm 1$, and $nq \pm 1$ ($m$ and $n$ being distinct integer numbers not exceeding $p$), when divided by $p$, give the same remainder, it is evident that their difference $(m-n)q$, must be divisible by $p$; now, this is impossible, because $q$ is prime to $p$, and $m-n$ is a number less than $p$. Therefore, since all the remainders in question are integer, positive numbers less than $p$, and different from each other, KK