※ 引述《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 and (c,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 a fraction a/b < x/y such that bx-ay=1. And then we can obtain another fraction (x-a)/(y-b)>x/y such that y(x-a)-x(y-b) =1. [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. Then we examine that (x-a)/(y-b) > x/y with y(x-a)-x(y-b)=1. About the fraction we just check x-a>0 and y-b>0 as discussed above. Since y(x-a)-x(y-b) = -ay+bx = 1, the fraction is greater than x/y. Finally we want to examine one more thing: b(x-a)-a(y-b) = bx - ay = 1. To conclude, for any fraction in its lowest term x/y with 1<x<y, there are two fractions a/b and c/d such that a/b < x/y < c/d bc-ad=1, bx-ay=1, cy-dx=1, a+c=x, and b+d=y. (L3) If a/b < x/y < c/d with bc-ad=1, then y≧b+d. (L4) If a/b < x/(b+d) < c/d with bc-ad=1, then (x-1)/(b+d) < a/b and (x+1)/(b+d) > c/d. 把这四条 Lemma 证出来本题应该就能证出来了吧(?)， 而这四条 Lemma 我似乎(?)也都证出来了，烦请各位先进指教。 == 未完待上完课再续 --

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