Prove this problem that involves Mathematical induction

[chwala]

Homework Statement

See attached

Relevant Equations

Mathematical induction

Ok, would i be correct to approach it this way,
Let $n=1$. If $n=1$, then $5^1+3$ is divisible by $4$, the statement is true for $n=1$.
Assume its true for $n=k$ ∀ $kε\mathbb{z}^{+}.$ Then $5^k+3$ is divisible by $4.$
i.e $5^k+3=4m$ ∀ $m ε\mathbb{z}^{+}$
Let $n=k+1.$ Then,
$5^{k+1} +3=5^{k+1} -5^k +5^k +3$
$=5^k(5-1)+5^k+3$
$=5^k(4)+5^k+3$
$=5^k(4)+m$

 

[fresh_42]

Homework Statement:: See attached
Relevant Equations:: Mathematical induction

View attachment 302050

View attachment 302051

Ok, would i be correct to approach it this way,
Let $n=1$. If $n=1$, then $5^1+3$ is divisible by $4$, the statement is true for $n=1$.
Assume its true for $n=k$ ∀ $kε\mathbb{z}^{+}.$ Then $5^k+3$ is divisible by $4$
i.e $5^k+3=4m$ ∀ $m ε\mathbb{z}^{+}$
Let $n=k+1$
$5^{k+1} +3=5^{k+1} -5^k +5^k +3$
$=5^k(5-1)+5^k+3$
$=5^k(4)+5^k+3$
$=5^k(4)+m$

Looks good, except that the induction base should be $n=0$.

And of course, it is easier to prove it by the fact that $\mathbb{Z}\longrightarrow \mathbb{Z}/4\mathbb{Z}$ given by $n\longmapsto n \pmod 4$ is a ring homomorphism, i.e. modulo respects addition and multiplication.

 

[chwala]

Looks good, except that the induction base should be $n=0$.

And of course, it is easier to prove it by the fact that $\mathbb{Z}\longrightarrow \mathbb{Z}/4\mathbb{Z}$ given by $n\longmapsto n \pmod 4$ is a ring homomorphism, i.e. modulo respects addition and multiplication.

For addition, i can see that $1+4=4+1=1$
and multiplication, $1⋅4=4⋅1=0$

 

[fresh_42]

For addition, i can see that $1+4=4+1=1$
and multiplication, $1⋅4=4⋅1=0$

It is $(5^n+3) \pmod 4 = 5^n \pmod 4 +3 \pmod 4= (5 \pmod 4)^n+ 3\pmod 4= 1^n \pmod 4 +3 \pmod 4=0 \pmod 4.$

 

[chwala]

It is $(5^n+3) \pmod 4 = 5^n \pmod 4 +3 \pmod 4= (5 \pmod 4)^n+ 3\pmod 4= 1^n \pmod 4 +3 \pmod 4=0 \pmod 4.$

Implying that for multiplication we shall end up with...

$1^n \pmod 4 ⋅3 \pmod 4=3⋅3=1 \pmod 4.$

 

[fresh_42]

Implying that for multiplication we shall end up with...

$1^n \pmod 4 ⋅3 \pmod 4=3⋅3=1 \pmod 4.$

No. $1\cdot 1= 1$. Not $3$.

 

[chwala]

No. $1\cdot 1= 1$. Not $3$.

Sorry let me get this right,
$1^n \pmod 4=3$
$3 \pmod 4=3$ Correct? and $3⋅3$ in$\mod 4=1$

 

[fresh_42]

Sorry let me get this right,
$1^n \pmod 4=3$
$3 \pmod 4=3$ Correct? and $3⋅3$ in$\mod 4=1$

No.
\begin{align*}
1 \pmod 4 &= 1\\
1\cdot 1 \pmod 4 &= 1\\
1\cdot 1 \cdot 1 \pmod 4&=1\\
\ldots &\ldots \\
1^n \pmod 4 &=1
\end{align*}

Where do you get the three from?
$$
\underbrace{\underbrace{1^n\pmod 4}_{=1}+\underbrace{3\pmod 4}_{=3}}_{=4 \pmod 4 =0}
$$

 

[chwala]

No.
\begin{align*}
1 \pmod 4 &= 1\\
1\cdot 1 \pmod 4 &= 1\\
1\cdot 1 \cdot 1 \pmod 4&=1\\
\ldots &\ldots \\
1^n \pmod 4 &=1
\end{align*}

Where do you get the three from?
$$
\underbrace{\underbrace{1^n\pmod 4}_{=1}+\underbrace{3\pmod 4}_{=3}}_{=4 \pmod 4 =0}
$$

True, i meant under 'multiplication' not 'addition modulo'