Question

induction, show using induction that 5 divides all numbers of the form 2^(4n-2) + 1

Answer 1

P(n) = \[5| 2^{4n-2}+1\]
p(1) = \[5| 2^{4(1)-2}+1 = 5|5\]

Answer 2

P(k)= \[5|2^{4k-2}+1\]

p(k+1) = \[5|2^{4(k+1)-2}+1 => 5| 2^{4k+2}+1\]

Answer 3

so you need to reduce P(k+1) to P(k) to show the relationship holds like if P(k+1) = 5*P(k) then that would show its true

Answer 4

For \(k + 1\) we get:
\[2^{4(k+1) - 2} +1 =2^{2(2(k+1)-1))} + 1= 2^{2(2k+1))} + 1 = 4^{(2k+1)} + 1 = 4^{2k}\cdot 4+1\]
Note that since \(4^2 \equiv 1\mod 5 \) the \( (4^2)^k\equiv 1^k \mod 5 = 1 \mod 5\). We can then show that:
\[4^{2k}\cdot 4+1 = 1^k \cdot 4 + 1\mod 5 = 4 + 1\mod 5 = 0 \mod 5\]
Which shows what we wanted to prove.

Answer 5

damn the spacing is making that hard to read.

Answer 6

For the hard to read parts:
\[4^2 \equiv 1\bmod5 \implies ({4^2})^k \equiv 1^k\bmod5\]
Then:
\[4^2k \cdot 4 + 1\equiv 1^k\cdot4 + 1\bmod 5 \equiv4+1 \bmod 5 \equiv 0 \bmod 5 \]

Answer 7

so you take 4^(2k)=1(mod5) and multiply both sides by (4+1)?

Answer 8

Ah no, its more like since \((4^k)^2 \equiv 1^k \bmod5\) then \( (4^2)^k \cdot 4 \equiv 1^k\cdot 4 \bmod 5 \) then add 1 to both sides to obtain the original form:
\[ (4^2)^k \cdot 4 + 1 = 4+ 1 \bmod5 = 0 \bmod 5\]