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