Show that ## (-13)^{n+1}\equiv (-13)^{n}+(-13)^{n-1}\pmod {181} ##?

[Math100]

Homework Statement

For $n\geq 1$, show that $(-13)^{n+1}\equiv (-13)^{n}+(-13)^{n-1}\pmod {181}$.
[Hint: Notice that $(-13)^{2}\equiv -13+1\pmod {181}$; use induction on $n$.]

Relevant Equations

None.

Proof:

The proof is by induction.
(1) When $n=1$, the statement is $(-13)^{1+1}\equiv (-13)^{1}+(-13)^{1-1}\pmod {181}\implies 169\equiv -12\pmod {181}$, which is true.
(2) Now assume the statement is true for some integer $n=k\geq 1$, that is assume $(-13)^{k+1}\equiv (-13)^{k}+(-13)^{k-1}\pmod {181}$. Next, we will show that the statement for $n=k+1$ is true. Observe that
\begin{align*}
(-13)^{(k+1)+1} &\equiv [(-13)^{k+1}+(-13)^{(k+1)-1}]\pmod{181}\\
&\implies (-13)^{k+2}\equiv [(-13)^{k+1}+(-13)^{k}] \pmod{181}.
\end{align*}
Thus
\begin{align*}
(-13)^{k+2}&\equiv (-13)(-13)^{k+1}\\
&\equiv (-13)[(-13)^{k}+(-13)^{k-1}]\pmod {181}\\
&\equiv [(-13)^{k+1}+(-13)^{k}]\pmod {181}.
\end{align*}
This establishes $(-13)^{k+2}\equiv [(-13)^{k+1}+(-13)^{k}]\pmod {181}$, which implies that the statement is true for $n=k+1$.
The proof by induction is complete.
Therefore, $(-13)^{n+1}\equiv (-13)^{n}+(-13)^{n-1}\pmod {181}$ for $n\geq 1$.

 

[fresh_42]

Homework Statement:: For $n\geq 1$, show that $(-13)^{n+1}\equiv (-13)^{n}+(-13)^{n-1}\pmod {181}$.
[Hint: Notice that $(-13)^{2}\equiv -13+1\pmod {181}$; use induction on $n$.]
Relevant Equations:: None.

Proof:

Almost.

There were back slashes missing at begin and end commands. I inserted them.

The proof is by induction.
(1) When $n=1$, the statement is $(-13)^{1+1}\equiv (-13)^{1}+(-13)^{1-1}\pmod {181}\implies 169\equiv -12\pmod {181}$, which is true.
(2) Now assume the statement is true for some integer $n=k\geq 1$, that is assume $(-13)^{k+1}\equiv (-13)^{k}+(-13)^{k-1}\pmod {181}$. Next, we will show that the statement for $n=k+1$ is true.

Simply erase the next paragraph. This looks as if you used the statement which has to be shown. So either you say "We must show that ..." instead of "observe" or better: drop it.

Observe that
\begin{align*}
(-13)^{(k+1)+1} &\equiv [(-13)^{k+1}+(-13)^{(k+1)-1}]\pmod{181}\\
&\implies (-13)^{k+2}\equiv [(-13)^{k+1}+(-13)^{k}] \pmod{181}.
\end{align*}

This now is the actual proof: ($(-13)^{k+2}$ + definition LHS + induction hypothesis + algebra = RHS)

Thus

\begin{align*}
(-13)^{k+2}&\equiv (-13)(-13)^{k+1}\\
&\equiv (-13)[(-13)^{k}+(-13)^{k-1}]\pmod {181}\\
&\equiv [(-13)^{k+1}+(-13)^{k}]\pmod {181}.
\end{align*}
This establishes $(-13)^{k+2}\equiv [(-13)^{k+1}+(-13)^{k}]\pmod {181}$, which implies that the statement is true for $n=k+1$.
The proof by induction is complete.
Therefore, $(-13)^{n+1}\equiv (-13)^{n}+(-13)^{n-1}\pmod {181}$ for $n\geq 1$.