อ้างอิง:
ข้อความเดิมเขียนโดยคุณ 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 ลงตัว
ดังนั้น ทฤษฎีบทดังกล่าวจึงจำเป็นและเพียงพอ
|
ขออนุญาตนำเสนอวิธีที่ไม่ใช้ทฤษฎีบท จริงๆแล้วก็อาจจะเป็นไอเดียการพิสูจน์ทฤษฎีบทนั้นก็ได้ครับ
พิจารณาลำดับ $F_n$ mod $13$
$1, 1, 2, 3, 5, 8, 0, 8, 8, ...$
เมื่อเกิด $0$ ขึ้นหลัง $x$ ซึ่ง $x\not= 0$ จะได้
$..., x, 0, x, x, 2x, 3x, 5x, 8x, 13x, ...$
ซึ่ง $13x$ คือ $0$ ใน mod $13$ นั่นเอง
ดังนั้นจะเกิด $0$ ขึ้นทุกๆ $7$ ตัว