※ 引述《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. 對 n 作數學歸納法 n=1,2 OK 設 n>2 先將分子分母均小於 n 的最簡分數由小到大排列 設 a/b < c/d 為相鄰分數,則由數學歸納法的假設,有以下事實: (1) bc-ad=1 (2) 若 a/b < x/y < c/d,則 y≧n (2)等價於以下(2') (2') 若 bx-ay≧1 且 dx-cy≦-1,則 y≧n 再排形如 k/n 或 n/k 最簡分數 設 k/n 會插入 a/b 與 c/d 中,即 a/b < k/n < c/d => bk-an≧1 且 dk-cn≦-1 => (2')的不等式有解(x,y)=(k,n) 但 (1) => (2')的不等式區域邊界頂點為格子點 => (k,n) 為邊界頂點 => bk-an=1 且 dk-cn=-1 (順便證了 k 的唯一性) n/k 證明亦同 又頭尾的分數必為 1/n,1/{n-1},..,{n-1}/1,n/1 故由數學歸納法得證 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.31.174