1. 개요
페리 수열(Farey sequence)은 0과 1 사이의 유리수 중에서 분모가 임의의 자연수를 넘지 않는 기약진분수를 오름차순으로 나열한 수열을 말한다.프랑스의 기하학자인 샤를 아로(Charles Haros)가 1802년에 도입 및 제안하였는데, 이 수열에 대해 14년이 지난 1816년에 영국의 지질학자 존 페리 1세(John Farey, Sr.)가 이 수열을 재발견해 이 수열에 대한 추측을 발표하였다. 이 추측은 이후에 오귀스탱루이 코시가 증명하였다.
페리 수열은 수학적으로 다음과 같이 정의할 수 있다.
[math(F_{n} : 0 \leq h \leq k \leq n)] 일 때, [math(gcd(h, ,k)=1)]을 만족하는 [math(\dfrac{h}k)]를 오름차순으로 나열한 수열이다.
예를 들면, [math(F_{1}=\{0,\,\,1\})]
[math(F_{2}=\{0,\dfrac{1}2,1\})]
[math(F_{3}=\{0,\dfrac{1}3,\dfrac{1}2, \dfrac{2}3, 1\})]
[math(F_{4}=\{0,\dfrac{1}4, \dfrac{1}3,\dfrac{1}2, \dfrac{2}3, \dfrac{3}4, 1\})]
[math(F_{5}=\{0,\dfrac{1}5, \dfrac{1}4,\dfrac{1}3, \dfrac{2}5, \dfrac{1}2, \dfrac{3}5, \dfrac{2}3, \dfrac{3}4, \dfrac{4}5, 1\})] ......
와 같이 표기할 수 있다.
2. 페리 수열의 정리 및 증명
정리 1
두 분수 [math(\dfrac{a}b)], [math(\dfrac{c}d)] 에 대해 [math(\dfrac{a}b)] [math(<)] [math(\dfrac{c}d)] 이라면, [math(\dfrac{a}b)] [math(<)] [math(\dfrac{a+c}{b+d})] [math(<)] [math(\dfrac{c}d)] 가 성립한다.
증명은,두 분수 [math(\dfrac{a}b)], [math(\dfrac{c}d)] 에 대해 [math(\dfrac{a}b)] [math(<)] [math(\dfrac{c}d)] 이라면, [math(\dfrac{a}b)] [math(<)] [math(\dfrac{a+c}{b+d})] [math(<)] [math(\dfrac{c}d)] 가 성립한다.
[math(\dfrac{a+c}{b+d})] [math(-)] [math(\dfrac{a}b)] [math(=)] [math(\dfrac{bc-ad}{b(b+d)})] [math(=)] [math(0)]
[math(\dfrac{c}{d})] [math(-)] [math(\dfrac{a+c}{b+d})] [math(=)] [math(\dfrac{bc-ad}{d(b+d)})] [math(=)] [math(0)] 이다.
정리 2
[math(0)] [math(\leq)] [math(\dfrac{a}{b})] [math(<)] [math(\dfrac{c}{d})] [math(\leq)] [math(1)] 이고 [math(bc-ad=1)]이면 [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 는 [math(F_{n})] 에서 바로 이웃하는 분수이다.
증명은,[math(0)] [math(\leq)] [math(\dfrac{a}{b})] [math(<)] [math(\dfrac{c}{d})] [math(\leq)] [math(1)] 이고 [math(bc-ad=1)]이면 [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 는 [math(F_{n})] 에서 바로 이웃하는 분수이다.
[math(bc-ad=1)]이라 했으니, [math(a, b)]는 서로소, [math(c, d)]는 서로소가 되므로 [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 는 기약분수이다.
그러므로, [math(\max(b, d) \leq {n})] 에서 [math(b, d)]는 모두 [math(n)] 이하이므로, [math(\dfrac{a}{b})], [math(\dfrac{c}{d}\in F_{n})] 이다.
또한, [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 가 [math(F_{n})] 에서 바로 이웃하는 분수가 아닌 경우, [math(\dfrac{a}{b} < \dfrac{p}{q} < \dfrac{c}{d})] 를 만족하는 [math(\dfrac{p}{q})] 가 존재하게 된다.
[math(bp-aq > 0)], [math(cq-dp > 0)] 이니 [math(bp-aq \ge 1)], [math(cq-dp \ge 1)] 이다.
주어진 조건에서 [math(bc-ad = 1)] 이라 하였으니,
[math(q = (bc-aq)q)] 라 할 수 있다. 이것을 [math(q)] 에 대해 정리하면, [math(q =b(cq-dp) +d(bp-ad))]이므로 [math(q \ge b+d)] 이다.
여기에서 주어진 조건이, [math(n \leq b+d-1)] 이므로, [math(\dfrac{p}{q})]는 [math(F_{n})]에 포함될 수 없다.
그러므로, [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 는 [math(F_{n})] 에서 연속적으로 이웃하는 분수가 된다.
정리 3
[math(0)] [math(\leq)] [math(\dfrac{a}{b})] [math(<)] [math(\dfrac{c}{d})] [math(\leq)] [math(1)] 이고, [math(bc-ad=1)]이면서 [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 가 [math(F_{n})] 에서 연속이고 [math(F_{n+1})]에서 연속이 아니라면, [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 사이에는 유일하게 [math(\dfrac{a+c}{b+d})] 가 들어갈 수 있다.
증명하자면,[math(0)] [math(\leq)] [math(\dfrac{a}{b})] [math(<)] [math(\dfrac{c}{d})] [math(\leq)] [math(1)] 이고, [math(bc-ad=1)]이면서 [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 가 [math(F_{n})] 에서 연속이고 [math(F_{n+1})]에서 연속이 아니라면, [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 사이에는 유일하게 [math(\dfrac{a+c}{b+d})] 가 들어갈 수 있다.
[math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 사이에 [math(\dfrac{p}{q})] 가 존재하기 위해서는, 위의 증명 2에서 언급된 [math(q \ge b+d)] 에 의거해, 다음처럼 유추할 수 있다.
즉, [math(q = b+d)] 일 때, [math(\dfrac{p}{q})] 가 존재한다.
[math(bc-ad=1)] 이고, [math(cq-dp=1)] 인 경우이므로, [math(bc-ad=cq-dp)] 이다.
[math(bc-ad=cq-dp)] 를 [math(p)] 로 정리하면, [math(p=a+c)]이다.
따라서, [math(\dfrac{p}{q} = \dfrac{a+c}{b+d})]가 [math(\dfrac{a}{b})] 와 [math(\dfrac{c}{d})] 사이에 유일하게 존재한다.