diophantine REVD

This is the Title PhL 3.26.05 Diophantine stuff ended up in GA, not in scrambler. Lemma: In the integer equation ax = by, the smallest solution for x is x = b/GCD(a,b). (4.22) Proof: A candidate solution of ax = by is x = b and y = a. If d ≡ GCD(a,b), then we know that an improved solution is x' = b/d and y' = a/d since x' and y' are both integers and a[b/d] = b[a/d]. Since by definition d is the largest common divisor of b and a, th Lemma: In the integer equation ax = by with a,b > 0, the smallest solution for x is x = b/GCD(a,b). (4.22) Proof: ax = by a/y = b/x ≡ β . The most general solution of ax = by then has this form: x = by/a = b/[a/y] = b/β y = ax/b = a/[b/x] = a/β We know that x = b and y = a is a solution of ax = by, and we seek solutions with x < b, so only values of β > 1 are of interest. In the reals, the any solution of ax = by would have the form x = b/β and y = a/β. Proof: A candidate solution of ax = by is x = b and y = a. If d ≡ GCD(a,b), then we know that an improved solution is x' = b/d and y' = a/d since x' and y' are both integers and a[b/d] = b[a/d]. Since by definition d is the largest common divisor of b and a, th Lemma: Consider the Diophantine [see App. G] equation ax = by where a and b are positive integers and we seek solutions where x and y are positive integers. The smallest solution for x is x = b/GCD(a,b). (4.22) Proof: Let d ≡ GCD(a,b). A candidate smallest solution for x is then x = b/d with y = a/d since these x and y values are both integers and since a[b/d] = b[a/d]. Suppose there were some solution pair x',y' such that x' < x. Since ax = by and ax' = by', if x' < x we must have y' < y. Then we can write x' = x - I and y' = y - J where both I and J are positive integers. Then ax' = by' a[x-I] = b[y-J] a[b/d - I] = b[a/d -J] aI = bJ Then x = I and y = J is another solution of ax = by. ************************************* Consider ax = by. Suppose d = gcd(a,b). Then divide ax=by by d to get Ix = J y. where I= a/d and J = b/d and gcd(I,J) = 1. Now, what is the smallest-x solution of Ix = Jy ? One solution is x = J and y = I. Suppose there were some other solution x = αJ and y = αI where α < 1. ****************************************** Consider the simpler problem: Suppose ax = by and gcd(a,b) =1. What is the smallest solution x ? We know that x = b and y = a is at least a solution. Why can't we have a solution of the form x = αb and y = αa for some fraction α like α = 2/3 ? Try to find a good example. a = 9 and b = 4. Then want x = α4 and y = α9. Try fraction α = I/J, then have x = (I/J)4 y = (I/J)9 How do I know that no I,J exist which make x and y integers? Try J = 4 for starters so x = I. Then we have to have y = I(9/4) but we need I < J so I < 4. But I has to cancel the 4. Remember theorem: Fact 2: Suppose GCD(N1,N2) = 1 and N1A = N2B. Then N2 divides A and N1 divides B. (G.2) How does this apply to ax = by? Write as Fact 2: Suppose GCD(a,b) = 1 and ax = by. Then b divides x and a divides y. (G.2) This tells us that x/b is an INTEGER. And y/a is an integer as well. They are the same integer. This is then new information. x/b = I = y/a ****************************************** Consider the simpler problem: Suppose ax = by and gcd(a,b) =1. What is the smallest solution x ? First of all, we can write ax = by => y/a = x/b ≡ α Then we can write x = by/a = α b y = ax/b = α a The smallest-x solution will be the smallest-α solution. But G.2 says that α must be a positive integer. Thus the smallest x solution is x = b. *********************************************************************** Fact 15: Consider the Diophantine equation ax = by where a,b > 0. Consider the set of solutions (x,y) in which x,y > 0. The solution with the smallest value of x is (x = b/d , y = a/d) where d = GCD(a,b). Proof: Let N1, N2 be the positive integers N1 = a/d, N2 = b/d. From Fact 1, GCD(N1,N2) = 1. Also, we see that ax = by N1x = N2y. The solutions (x,y) of these two equations are the same, so the smallest-x solution will be the same. We shall then attempt to determine the smallest-x solution of N1x = N2y. According to Fact 2 with A = x and B = y, we know, since GCD(N1,N2) = 1 and N1x = N2y, that x/N2 = y/N1 = I, a positive integer, Thus, solutions of N1x = N2y are x = IN2 and y = IN1 where I is a positive integer. The smallest-x solution must then be x = N2 and y = I1. This is then also the smallest-x solution of equation ax = by. Thus, the smallest-x solution of ax = by is x = b/d and y = a/d. QED ***************************************