※ 引述《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