- #1
Math100
- 768
- 219
- 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 ##.
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 ##.
Last edited: