Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q7

My Solution for "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$.]"

Ran

15 Dec 2023

Background

All theorems, corollaries, and definitions listed in the book's order:

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.

< Chapter 4.2, Q6 Chapter 4.2, Q8 >

Math Number Theory Solution

Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q7

Table of Contents

Background

Question

Solution

Ran

Comments

Table of Contents

Background

Question

Solution

Related Pages

Ran

Ranblog Newsletter

Comments

You might also like

Basic Techniques for Solving Theory of Congruence Problems - 1 Paid Members Public

Elementary Number Theory Problems 4.3 Solution (David M. Burton's 7th Edition) - Q9 Paid Members Public