피보나치 수열 mod M의 주기

정의. 수열 a(1), a(2), ...이 있을 때, 양의 정수 T가 존재하여 모든 양의 정수 n에 대해 a(n) = a(n+T)이면, 이 수열을 주기 수열이라고 합니다. 

보조정리. 유한집합 A에서 A로 가는 일대일 대응 함수 f, 그리고 A의 한 원소 x에 대해, 수열 x, f(x), f(f(x)), ...은 주기 수열입니다.

증명. |A| = m이라고 할 때, 비둘기집의 원리에 의해 a(1), ..., a(m+1) 중에는 같은 원소가 두 개 존재합니다. a(x) = a(y), x < y라고 하고, T = y-x로 둡시다. 그러면 모든 양의 정수 n >= x에 대해 a(n) = a(n+T)입니다. 증명은 귀납법으로 할 수 있습니다. n = x일 때 가정에 의해 a(n) = a(n+T)입니다. 또한 a(n) = a(n+T)라면, a(n+1) = f(a(n)) = f(a(n+T)) = f(n+1+T)입니다.

게다가 모든 양의 정수 n <= x에 대해서도 a(n) = a(n+T)입니다. 귀납법으로 증명하되, 이번에는 x에서 시작해서 내려갑니다. f가 일대일 대응이므로 역함수 f^-1이 존재합니다. a(n) = a(n+T)라면, a(n-1) = f^-1(a(n)) = f^-1(a(n+T)) = a(n-1+T)입니다.

정리. F(1) = F(2) = 1, F(n+2) = F(n) + F(n+1)이라고 할 때, F(n)을 M으로 나눈 나머지로 이루어진 수열은 주기 수열입니다.

증명. 집합 A = {(x,y) | 0<=x,y<M; x, y는 정수} 의 원소로 이루어진 수열을 다음과 같이 정의합시다. 

• a(1) = (0, 1)
• a(2) = (1, 1)
• a(n)을 (L, R)이라고 할 때, a(n+1) = (R, (L+R을 M으로 나눈 나머지))

A에서 A로 가는 함수 f를 f((L, R)) = (R, (L+R을 M으로 나눈 나머지))로 정의합시다. 이 f가 일대일 대응 함수임을 증명하면, a가 주기 수열임을 보이게 되고, 따라서 F는 주기 수열입니다.

f((L, R)) = f((X, Y))라고 합시다. 그러면 첫 번째 원소가 같으므로 R = Y이고, 그러면 L+R을 M으로 나눈 나머지와 X+R을 M으로 나눈 나머지가 같고, L, X는 0 이상 M 미만이므로 L = X입니다. 따라서 (L, R) = (X, Y)이고 f는 단사함수입니다.

또한 f(L, R) = (x, y)인 L, R은 존재합니다. L = (y-x를 M으로 나눈 나머지), R = x로 두면 됩니다. 따라서 f는 전사함수입니다.

주석

여기서 f가 일대일 대응임을 증명한 이유는, 비둘기집의 원리로는 "수열이 특정 시점부터 주기를 이룬다"까지만 증명할 수 있기 때문입니다.