164 SPECIAL TOPICS IN THEORETICAL ARITHMETIC

409. Th. If (x1, y1) is a solution, if x;» = x; (mod b) and
Y2 = (¢ — axy) : b, then y, is an integer and (x2, y2) is a solution.

Since (x1, 1) is a solution, ax; + by, =

Since x; = x; (mod b), ¢ — ax; = ¢ — ax; (mod b)

But ¢ — ax; = by, and by; = 0 (mod d)

Hence ¢ — ax: = 0 (mod b)

Therfor ¢ — axs > b

Hence y, is an integer.

Also by § 398 (x2, ¥2) is a solution.

410. Th. Ifal+bm = 1,1=1 (modb), ¢ = ¢; (mod b),
her = %2 (mod b), and y, = (¢ — axz) : b, then y, is an integer
and (xs2, vs) 1s a solution.
For, since ! = I, (mod b) and ¢ = ¢; (mod b), Ic = l,¢;, (mod b)
Then, if we put x; = Ic and y, = mc, (%1, y1) is a solution.
Then x; = Ic = lic; = %2 (mod b)
Hence x; = x, and x; = x; (mod d)
Then by the preceding theorem (x,, ¥,) is a solution.

411. The advantage of this theorem is that we may fre-
quently choose for /;, ¢;, and x; numbers numerically smaller
than /, ¢, and /i¢; respectivly.

Then, since |L| < |I| and |a1| < |¢|, |ha| < |ic]

And, since |x:| < |hal, |x| < ||

So that we will have obtaind a solution (xs, y.) whose x is
numerically smaller than the x of the solution (¢, mc).

We might similarly work to diminish numerically the y of
the solution (J¢, mc), namely mc.

Example. 49x + 19y = 900
a =49, b=19, ¢ =900 47
I =7, m= —18 19/ 900
I =7(mod19) ¢=7 (mod19) S
l1 = 7, 1 = 7 m
Loy = 49 = 11 (mod 19) 133
Take x, = 11 i

Yo = (c —axy) : b =19
Then (11,19) is a solution and (11 4 19z, 19 — 49%) is a
complete solution, simpler than that of §408.