[Switchgear]

ข้อ 17. กำหนดลำดับฟิโบนักชี (Finbonacci) $F_1, F_2, F_3, ?$ โดยที่ $F_1 = F_2 = 1$ และ $F_{n+1} = F_n + F_{n-1}$
เมื่อ $n \geqslant 2\;$ ให้ $X = \{n | 1 \leqslant n \leqslant 1000$ และ $13$ เป็นตัวประกอบของ $Fn \}$ จงหา $|X|$

เฉลยวิธีทำ: (อาศัยทฤษฎีบทที่แน่นอน)

อาศัยทฤษฎีบทที่ว่า ?สำหรับจำนวนเฉพาะ p ใดๆ, มีจำนวนฟิโบนักชีนับอนันต์ ที่สามารถหารด้วย p ลงตัว
และจำนวนทั้งหมดอยู่ห่างเท่าๆ กันในลำดับฟิโบนักชี (For any prime p, there are infinitely many
Fibonacci numbers that are divisible by p and these are all equally spaced in the
Fibonacci sequence)? ซึ่งผมอ้างอิงจากหน้า 287 ในหนังสือ Elementary Number Thoery,
David M. Burton, sixth edition, 2007. (มีบทพิสูจน์สมบูรณ์ในเล่มดังกล่าวด้วย)

ดังนั้นสิ่งที่เราต้องหา ก็คือ ลำดับของจำนวนฟิโบนักชีตัวแรกสุดที่หารด้วย $13$ ลงตัว ซึ่งเราพบว่า $7$ ตัวแรก
ของลำดับฟิโบนักชีมีดังนี้ $1, 1, 2, 3, 5, 8, 13$ นั่นคือลำดับที่ $7$ หารด้วย $13$ ลงตัว แปลว่า ทุกตัวที่อยู่
ในลำดับซึ่งเป็นพหุคูณของ $7$ ย่อมหารด้วย $13$ ลงตัวด้วย

เนื่องจาก $1000 = 7 \times 142 + 6$ จึงมีจำนวนฟิโบนักชีอยู่ $142$ ตัวที่หารด้วย $13$ ลงตัวในช่วง
$1 \leqslant n \leqslant 1000$ ตามเงื่อนไขในโจทย์ นั่นคือ $|X| = 142$ เป็นคำตอบที่ต้องการ

หมายเหตุ: ข้อนี้หากไม่อ้างหรือไม่รู้ทฤษฎีบท ก็ไม่มีทางมั่นใจได้ว่าทุกๆ 7 ลำดับจะหารด้วย 13 ลงตัวหรือไม่
ต่อให้เราทดลองบวกไปถึงลำดับที่ 21 แล้วหาร 13 ลงตัว ก็ไม่ได้แปลว่าลำดับที่ 28 จะหารด้วย 13 ลงตัว
ดังนั้น ทฤษฎีบทดังกล่าวจึงจำเป็นและเพียงพอ