Prove $\forall n\ge0,43\mid 6^{n+2}+7^{2n+1}$ in three ways

Question

Prove that $\forall n\ge0,43\mid 6^{n+2}+7^{2n+1}$ in three ways:

a) Use mathematical induction

b) Using techniques of modular arithmetic

c) Without induction, nor modular arithmetic (Hint: use binomial theorem.)

a)

Proof.

Base case: $n=0$

WTS $\exists k\in\mathbb{Z},s.t. 6^{(0)+2}+7^{2(0)+1}=43k$

Let $k=1$, we have:

$$36+7=43\tag*{hold}$$

Inductive step:

Assume$$\exists k_1\in\mathbb{Z},s.t. 43k_1=6^{(j)+2}+7^{2(j)+1}$$

Show$$\exists k_2\in\mathbb{Z},s.t. 43k_2=6^{(j+1)+2}+7^{2(j+1)+1}$$

Let $$k_2=6k_1+7^{2j+1}$$

That $$43k_2=43(6k_1+7^{2j+1})=6(43k_1)+43(7^{2j+1})$$

By assumption $43k_1=6^{j+2}+7^{2j+1}$ have $$=6(6^{j+2}+7^{2j+1})+43(7^{2j+1})$$ $$=6(6^{j+2}+7^{2j+1})+301(7^{2j})$$ $$=6(6^{j+2}+7^{2j+1})+343(7^{2j})-42(7^{2j})$$ $$=6(6^{j+2}+7^{2j+1})+7^{2j+3}-6(7^{2j+1})$$ $$=6(6^{j+2}+7^{2j+1})-6(7^{2j+1})+7^{2j+3}$$ $$=6(6^{j+2}+7^{2j+1}-7^{2j+1})+7^{2j+3}$$ $$=6^{j+3}+7^{2j+3}=6^{(j+1)+2}+7^{2(j+1)+1}\tag*{$\square$}$$

b) $$\text{WTS }\forall x\ge0,6^{n+2}+7^{2n+1}\equiv0(\text{mod }43)$$

I first checked some "techniques of modular arithmetics" $\dots$

Theorem 3.1.2

if $a\equiv b(\text{mod m})$ and $b\equiv c\text{(mod }m)$, then $a\equiv c(\text{mod m})$

Theorem 3.1.3

When $a$ and $b$ are nonnegative integers, the relationship $a\equiv b\text{(mod }m)$ is equivalent to $a$ and $b$ leaving equal remainders upon division by $m$

Theorem 3.1.4

For a given modulus $m$, each integer is congruent to exactly one of the numbers in the set $\{0,1,2,\dots,m-1\}.$

Theorem 3.1.5

If $a\equiv b(\text{mod }m)$ and $c\equiv d(\text{mod }m)$, then

$i)(a+c)\equiv(b+d)(\text{mod }m)$

$ii)ac\equiv bd(\text{mod }m)$

Theorem 3.1.6

If $a\equiv b\text{(mod }m)$, then $a^n\equiv b^n\text{(mod }m)$, for every natual number n.

(from UTM "A Readable Introduction to Real Mathmatics" Chapter 3)

Proof.

$$\vdots$$

c) $$\text{WTS }\forall n\ge0,43\mid 6^{n+2}+7^{2n+1}$$

Proof.

Let $n\ge0$

Show $\exists k\in\mathbb{Z},s.t. 43k=6^{n+2}+7^{2n+1}$

Rough work:

$$6^{n+2}+7^{2n+1}=6^{n+2}+\frac{7^{2n+2}}{7}=6^{n+2}+\frac{(7^2)^{n+1}}{7}$$ $$=6^{n+2}+\frac{(43+6)^{n+1}}{7}=6^{n+2}+\frac{{n+1\choose0}43^{n+1}+\dots+{n+1\choose n}(43)6^{n}+{n+1\choose n+1}6^{n+1}}{7}$$ $$=\frac{7(6^{n+2})+6^{n+1}}{7}+\frac{{n+1\choose0}43^{n+1}+\dots+{n+1\choose n}(43)6^{n}}{7}$$ $$=\frac{42(6^{n+1})+6^{n+1}}{7}+\frac{{n+1\choose0}43^{n+1}+\dots+{n+1\choose n}(43)6^{n}}{7}$$ $$=\frac{6^{n+1}(42+1)}{7}+\frac{{n+1\choose0}43^{n+1}+\dots+{n+1\choose n}(43)6^{n}}{7}$$ $$=43(\frac{6^{n+1}+{n+1\choose0}43^{n}+\dots+{n+1\choose n}6^{n}}{7})$$

Therefore I suppose to let $k=\frac{6^{n+1}+{n+1\choose0}43^{n}+\dots+{n+1\choose n}6^{n}}{7}$, but how do I prove this $k\in\mathbb{Z}$?

Where should I start for b) ?

Any help or hint or suggestion would be appreciated.

Answer 1

For an alternative method:

Let $a_n=6*{n+2}+7^{2n+1}=36\times 6^n+7\times 49^n$

Then, of course $a_0=36+7=43$ and $a_1=559=43\times 13$.

We remark that $6$, $49$ are roots of $$p(x)=(x-6)(x-49)=x^2 - 55 x + 294$$

Thus the $a_n$ satisfy the linear recurrence $$a_n=55a_{n-1}-294a_{n-2}$$

Since $a_0, a_1$ are both divisible by $43$ it follows from a trivial induction that all the $a_n$ are.

Note: we never needed the explicit form of the recursion, just that the sequence did satisfy a linear recursion over the integers.

Answer 2

You have:

• $6^{0+2}\equiv36\pmod{43}$;
• $6^{1+2}\equiv1\pmod{43}$;
• $6^{2+2}\equiv6\pmod{43}$

and then you start all over again ($36$, $1$, $6$, $36$, …). Also, you have:

• $7^{2\times0+1}\equiv7\pmod{43}$;
• $7^{2\times1+1}\equiv42\pmod{43}$;
• $7^{2\times2+1}\equiv37\pmod{43}$

and then you also start all over again. Since $36+7\equiv0\pmod{43}$, $1+42\equiv0\pmod{43}$, and $6+37\equiv0\pmod{43}$, you're done.

Answer 3

Proof of (b)

First note that $6^3\equiv 1\text{(mod }43)$. Now consider

$$6^{2n+1}(6^{n+2}+7^{2n+1})\equiv 6^{3n+3}+42^{2n+1} \equiv 1-1 \equiv 0\text{(mod }43).$$

Therefore $$6^{n+2}+7^{2n+1} \equiv 0\text{(mod }43).$$

Proof of (c)

$$6^{n+2}+7^{2n+1}=36(6^n)+7(6+43)^n=(36+7)6^n+ \text {a multiple of 43}$$

and hence the result.

Answer 4

It is a one liner: $$36\times6^n+49^n\times 7\equiv -7\cdot 6^n+6^n\times 7$$

Answer 5

$(a):$

If $f(n)=6^{n+2}+7^{2n+1},$

Eliminate one of $6^n,7^{2n}$

$f(n+1)-6f(n)=?$

Or $f(n+1)-7^2f(n)=?$

Observe that both are divisible by $43$

So, if $43$ divides $f(n),43$ must divide $f(n+1)$

$(b)$

$7^2\equiv6\pmod{43}\implies7^{2n}=(7^2)^n\equiv6^n$

$(c)$

$7^{2n}=(7^2)^n=(6+43)^n=6^n+$ terms containing $43$

Generalization:

$$(m+1)^{2n+1}+m^{n+2}$$ is divisible by $m(m+1)+1$

Answer 6

(a) Let $x_n = 6^{n+2}+7^{2n+1} = 36\cdot 6^n+ 7\cdot 49^n$. Then $x_{n+2} = (6+49)x_{n+1}-(6\cdot 49)x_n$. The claim follows by induction since $x_0=43$ and $x_1= 559$ are both multiples of $43$.

(b) $6^{n+2}+7^{2n+1} = 36\cdot 6^n+ 7\cdot 49^n \equiv 36\cdot 6^n+ 7\cdot 6^n = 43 \cdot 6^n \equiv 0 \bmod 43$.

(c) $6^{n+2}+7^{2n+1} = 36\cdot 6^n+ 7\cdot 49^n = 36\cdot 6^n + 7(43+6)^n = 36\cdot 6^n + 7(43a+6^n) = 43\cdot 6^n+43a$

Answer 7

$6^2 = 36 \equiv -7 \pmod {43}$.

And $7^2=49\equiv 6 \pmod {43}$.

So $6^{n+2}\equiv 6^n6^2 \equiv (7^2)^n(-7)\equiv -7^{2n+1}\pmod {43}$.

So $6^{n+2} + 7^{2n+1}\equiv 0\pmod {43}$ and

so $43$ divides $6^{n+2} + 7^{2n+1}$.

Answer 8

We can answer the question using Theorem 3.16 from your stated theorems. $6^{n+2}+7^{2n+1}$ can be rewritten as

(1) $$36 \cdot 6^n + 7 \cdot 49^n$$

Let's examine $49^n$.

$$49^n = (43+6)^n$$

And since $43 + 6 \equiv 6$ mod 43, from theorem 3.16, we have $49^n \equiv 6^n$ mod 43. So we can replace $49^n$ with $6^n$ in (1):

$$36 \cdot 6^n + 7 \cdot 6^n = 43 \cdot 6^n \equiv 0$$mod(43)

So the original expression is divisible by 43.