※ 引述《chliao2006 (chien)》之铭言： : Let n be a fixed positive integer, : and suppose we list in increasing order all numbers a/b , : where 1 <= a,b <= n , and the fraction a/b is in lowest terms. : Show that if a/b and c/d are consecutive fractions in this list, : then bc - ad = 1. 先证四条引理，以下 a, b, c, d 都是正整数. (L1) If bc-ad=1, then (a,b)=1, (c,d)=1, (a,c)=1 and (b,d)=1. [Pf] Suppose (a,b)=p>1. Put a=ph, b=pk. Then bc-ad = pkc - phd = p(kc-hd)≠1. (L2) For any fraction in its lowest term x/y with 1<x<y, there exists two fractions a/b and c/d such that a/b < x/y < c/d ≦1, bx-ay=1, cy-dx=1, bc-ad=1, x=a+c and y=b+d. [Pf] Let x, y be two positive integers such that (x,y)=1 and 1<x<y. Then there are two unique integers q, r satisfying that y = xq + r and 0<r<x. Since (x,r)=(x,y)=1, there exists some integer a such that 0<a<x and ar≡-1 (mod x). Put ar = px-1. Then px-1 = ar < xr => px-rx<1 => x(p-r)<1 => p≦r. And since px-1 = ar >0, px>1 => p≧1. Let b = aq + p. Then bx-ay = (aq+p)x - a(xq+r) = px-ar = 1. Furthermore, b = aq+p < xq+p ≦ xq+r = y. Since bx-ay=1>0, bx>ay, a/b < x/y. Since x-a>0 and y-b>0 as discussed above, put c=x-a and d=y-b. Then cy-dx = (x-a)y - (y-b)x = -ay+bx =1>0. Hence x/y < c/d. And we claim c/d≦1. For if c=d+k for some k≧1, Then cy-dx = (d+k)y-dx = d(y-x)+ky > d+ky >1. (L3) If a/b < x/y < c/d with bc-ad=1 and bx-ay=1, then y≧b+d. [Pf] Let a/b < c/d with bc-ad=1 be given. Suppose there are some fraction x/y with y<b+d such that a/b < x/y < c/d and bx-ay=1. Since a/b < x/y < c/d, x/y - a/b < c/d - a/b. => 1/by < 1/bd => d > y≧b+d. (→←) (L4) If a/b < x/y < c/d with bx-ay=1 and cy-dx=1, then (x-1)/y≦a/b and (x+1)/y≧c/d. [Pf] a/b - (x-1)/y = [ay-b(x-1)]/by = (-1+b)/by≧0. (x+1)/y - c/d = [d(x+1)-cy]/dy = (-1+d)/dy≧0. Having proved the lemmas, we now proceed to build the argument by induction. Since the sequence are symmetric, we discuss only the left half part of the sequence, i.e., the terms not greater than 1/1. S_1 ={1/1} S_2 ={1/2, 1/1} S_3 ={1/3, 1/2, 2/3, 1/1} We observed that S_1, S_2, S_3 are such sequencese that every term is of the form a/b where 1≦a, b≦n, and is in its lowest term, and that for every two consecutive terms a/b < c/d, bc-ad=1. And apparently, 1/n is always the first term in S_n. Let S_k be such a sequence. Then we are proceeding to construct S_(k+1) as a such sequence. First we locate 1/(k+1) before 1/k and (k+1)*1 - 1*k =1. Then let x/(k+1) with 1<x<k+1 be any fraction in its lowest term. By Lemma 2, there are two fractions p/q and r/s such that p/q < x/(k+1) < r/s≦1 where xq-p(k+1) = r(k+1)-sx = qr-ps =1, x=p+r and k+1=q+s. Since q<k+1, s<k+1, p/q < r/s ≦1, these two fractions p/q and r/s must be in S_k. Hence we can just put x/(k+1) between p/q and r/s. But is there any other term of S_k between p/q and r/s? Suppose there is some term of S_k u/v≠r/s following p/q. Then qu-pv=1, and v≦k < k+1 = q+s. By Lemma 3, it is impossible. Hence in S_k p/q and r/s must be consecutive. By Lemma 4, since p/q < x/(k+1) < r/s and qx-p(k+1) = r(k+1)-sx = 1, (x-1)/(k+1) and (x+1)/(k+1) will not be between p/q and r/s. Thus p/q < x/(k+1) < r/s are exactly consecutive in S_(k+1). 总算写完了... 不过证明写得不太好，尤其是L2卡了好久 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.44.5.108