Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q7
Background
All theorems, corollaries, and definitions listed in the book's order:
Theorems and Corollaries in Elementary Number Theory
All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 4)
I will only use theorems or facts that are proved before this question. So you will not see that I quote theorems or facts from the later chapters.
Question
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$.]
Solution
We can prove the statement by using mathematical induction.
Base Case:
For $n = 1$, $(-13)^{2} \equiv -13 + 1 \pmod {181}$.
Induction Hypothesis:
Assume $(-13)^{k + 1} \equiv (-13)^{k} + (-13) ^{k - 1} \pmod {181}$.
Consider the case for $k + 1$:
$$ \begin{equation} \begin{split} (-13)^{k + 2} & \equiv (-13)(-13)^{k + 1} \\ & \equiv (-13)[(-13)^{k} + (-13) ^{k - 1}] \quad \text{by Induction Hypothesis} \\ & \equiv (-13)^{k + 1} + (-13) ^{k} \pmod {181} \end{split} \nonumber \end{equation} $$Conclusion:
This proves the statement by induction.
Read More: All My Solutions for This Book