سوال ۲۵

می‌دانیم که عدد $n$ام فیبوناچی٬ یا $F_n$ به این صورت تعریف می‌شود: $F_۰ = ۰$٬ $F_۱ = 1$ و $F_n = F_{n-۱} + F{n-۲}$ برای $۲ \le n$. برای چه تعداد $۰ \le n \le ۱۰۰$ عدد $F_n$ بر ۱۳ بخش‌پذیر است؟

  1. ۹
  2. ۱۱
  3. ۱۳
  4. ۱۵
  5. ۱۷

پاسخ

گزینه (۴) درست است.

می‌دانیم باقی‌مانده مجموع دو عدد در تقسیم بر ۱۳(یا هر عدد دیگری) با باقی‌مانده مجموع باقی‌مانده‌های آن دو عدد در تقسیم بر ۱۳ برابر است. بنابراین باقی‌مانده$F_i$ به ازای $i$ از ۱ تا ۱۰۰ در تقسیم بر ۱۳ مطابق جدول زیر خواهد بود که دوره تناوبی برابر ۲۸ دارد. همان‌طور که مشاهده می‌شود تعداد مضارب ۱۳ در بین آن اعداد برابر $[\frac{100}{7}+1]$ یا ۱۵ می‌باشد.