| [ QuizWit ] in KIDS 글 쓴 이(By): birdeee (별사랑이) 날 짜 (Date): 2008년 12월 10일 (수) 오후 11시 33분 32초 제 목(Title): Re: 저도 뭡置_ 문제 하나 질문이요 피보나치 수열을 k로 나눈 나머지는 k가지가 가능합니다. 두 개의 연속한 항을 각각 k로 나눈 나머지의 순서쌍 (a_n, a_{n+1})은 기껏해야 k^2개가 있습니다. 따라서 (a_n, a_{n+1})이라는 순서쌍의 수열은 언젠가 같은 항이 나옵니다. 같아지는 때가 x, y (x < y)라고 하겠습니다. a_x = a_y a_{x+1} = a_{y+1}이라고 하면 피보나치 수열의 성질에 의해 a_{x-1} = a_{y-1}이 됩니다. 다시 말해 피보나치 수열을 k로 나눈 나머지는 y-x번마다 반복됩니다. (물론 주기는 더 짧을 수도 있습니다.) 이 때 a_{y-x} = a_0 = 0 이어야 합니다. |