Theorem 4.3. Let a, b, r0,...,r+1 and q1,...,q be as in Theorem 4.1. Dene intege
ID: 3196379 • Letter: T
Question
Theorem 4.3.
Let a, b, r0,...,r+1 and q1,...,q be as in Theorem 4.1. Dene integers s0,...,s+1 and t0,...,t+1 as follows:
s0 := 1, t0 := 0,
s1 := 0, t1 := 1,
si+1 := si1 siqi, ti+1 := ti1 tiqi (i = 1,...,).
Then: (i) for i = 0,...,+1,wehave asi+bti =ri;inparticular, as+bt =gcd(a,b); (ii) for i = 0,...,, we have siti+1 tisi+1 = (1)i; (iii) for i = 0,..., +1, we have gcd(si,ti) = 1; (iv) for i = 0,...,, we have titi+1 0 and |ti| |ti+1|; for i = 1,...,, we have sisi+1 0 and |si||si+1|; (v) for i = 1,..., +1, we have ri1|ti| a and ri1|si| b; (vi) if a > 0, then for i = 1,..., + 1, we have |ti| a and |si| b; if a > 1 and b > 0, then |t| a/2 and |s| b/2.
EXERCISE 4.9. Assume notation as in Theorem 4.3. Show that:
(a) for all i = 2,...,, we have |ti| < |ti+1| and ri1|ti| < a, and that for all i = 3,...,, we have|si| < |si+1|and ri1|si| < b;
(b) siti 0 for i = 0,..., +1;
(c) if d := gcd(a,b) > 0, then|s+1| = b/d and|t+1| = a/d.
Explanation / Answer
Proof. (i) is easily proved by induction on i. For i = 0, 1, the statement is clear.
For i = 2, . . . , + 1, we have
asi + bti = a(si2 si1qi1) + b(ti2 ti1qi1) = (asi2 + bti2) (asi1 + bti1)qi1 = ri2 ri1qi1 (by induction)
= ri.
(ii) is also easily proved by induction on i. For i = 0, the statement is clear. For i = 1,...,, we have
siti+1 tisi+1 = si(ti1 tiqi) ti(si1 siqi)
= (si1ti ti1si) (after expanding and simplifying)
= (1)i1 (by induction) = (1)i.
(iii) follows directly from (ii).
For (iv), one can easily prove both statements by induction on i. The state- ment involving the ti’s is clearly true for i = 0. For i = 1,...,, we have ti+1 = ti1 tiqi; moreover, by the induction hypothesis, ti1 and ti have opposite signs and |ti| |ti1|; it follows that |ti+1| = |ti1| + |ti|qi |ti|, and that the sign of ti+1 is the opposite of that of ti. The proof of the statement involving the si’s is the same, except that we start the induction at i = 1.
For (v), one considers the two equations:
asi1 + bti1 = ri1,
asi + bti = ri.
Subtracting ti1 times the second equation from ti times the first, and applying (ii), we get ±a = tiri1 ti1ri; consequently, using the fact that ti and ti1 have opposite sign, we obtain
a = |tiri1 ti1ri| = |ti|ri1 + |ti1|ri |ti|ri1.
The inequality involving si follows similarly, subtracting si1 times the second equation from si times the first.
(vi) follows from (v) and the following observations: if a > 0, then ri1 > 0 for i=1,...,+1;ifa>1andb>0,then>0andr1 2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.