โจทย์ พิสูจน์หารด้วย 13 ลงตัว

[ohmohm]

เมื่อ n เป็นจำนวนเต็มบวก ให้พิสูจน์ว่า
$13 | (4\times 4^{2n} + 9\times 3^n)$
ขอบคุณครับ

[Thamma]

Induction on $ \unicode{8469} $

[nooonuii]

ข้อความเดิมเขียนโดยคุณ ohmohm

เมื่อ n เป็นจำนวนเต็มบวก ให้พิสูจน์ว่า
$13 | (4\times 4^{2n} + 9\times 3^n)$
ขอบคุณครับ

$4\cdot 4^{2n} + 9\cdot 3^n\equiv 4\cdot 3^n+9\cdot 3^n \equiv 0 \pmod{13}$

[ohmohm]

$4\times 4^{2(0)} + 9\times 3^{(0)} = 4+9 = 13$
$4\times 4^{2(1)} + 9\times 3^{(1)} = 64+27 = (13\times 5 - 1)+(13\times 2 + 1) = 91 = 13\times 7$

สมมติ $13$ หาร $(4\times 4^{2(k)} + 9\times 3^{(k)})$ ลงตัว คือได้เศษ $0$ สมมติว่า $13$ หาร $4\times 4^{2(k)}$ ได้เศษ $r$ จะได้ว่า $13$ หาร $9\times 3^{(k)}$ ได้เศษ $13-r$ จากนั้นจะมีจำนวนเต็ม $m_{1}$ และ $m_{2}$ ที่ทำให้
$4\times 4^{2(k)} = 13m_{1} + r$ และ
$9\times 3^{(k)} = 13m_{2} + 13 - r = 13(m_{2}-1) - r$

จากนั้นจะได้ว่า
$4\times 4^{2(k+1)} = 16\times 4\times 4^{2(k)}$
$= 16\times (13m_{1} + r)$
$= 16\times 13m_{1} + 16r$
และ
$9\times 3^{(k+1)} = 3\times 9\times 3^{(k)}$
$= 3\times 13(m_{2}-1) - 3r$

นั้นคือ $13$ หาร $(4\times 4^{2(k+1)} + 9\times 3^{(k+1)})$ ได้เศษ $16r-3r=13r$ ซึ่งหารด้วย 13 ลงตัว

ขอบคุณครับ