# Proofing divisibility by 77

Assignment:
Proof by induction that 7|(2n+1+32k−1)7|(2^{n+1}+3^{2k-1}) for all n≥1n\geq 1

I skip the test with n=1n=1

let n=kn=k
assume it’s true for some kk, then

a∈Na\in N

2k+1+32k−1=7a2^{k+1}+3^{2k-1}=7a

2k+1=7a−32k−12^{k+1}=7a-3^{2k-1}

Let n=k+1n=k+1

2k+2+32(k+1)−1=2(2k+1)+32k+12^{k+2}+3^{2(k+1)-1}=2(2^{k+1})+3^{2k+1}

Insert assumption:

=2(7a−32k−1)+32k+1=2(7a-3^{2k-1})+3^{2k+1}

=14a−2(32k−1)+32k+1=14a-2(3^{2k-1})+3^{2k+1}

Since 1414 is divisible by 77 it can be dropped of the equasion. (but how to do it rigorous?)
2(−32k−1)+32k+1=(−32k)23+3(32k)=32k(3−23)=32k(73)=7(32k3)\begin{align}
2(-3^{2k-1})+3^{2k+1}& =(-3^{2k})\frac{2}{3}+3(3^{2k})\\
&=3^{2k}(3-\frac{2}{3})\\
&=3^{2k}(\frac{7}{3})\\
&=7(\frac{3^{2k}}{3})
\end{align}
(what to say here?)

=================

32k3=32k−1\frac{3^{2k}}{3}=3^{2k-1} which should be a natural number
– MikeP
2 days ago

1

“aa divides bb” is written a∣ba\mid b, not b∣ab\mid a.
– Wojowu
2 days ago

=================

2

=================

Your last expression is 7(32k−1)7(3^{2k-1}). Since k≥1k\geq 1, 32k−13^{2k-1} is an integer.

To make things more rigourous, you can keep the term or use the notation

14a−2(32k−1)+32k+1≡−2(32k−1)+32k+1mod7 14a-2(3^{2k-1})+3^{2k+1} \equiv -2(3^{2k-1})+3^{2k+1} \mod 7

or you can just keep the terms there in every equation.

ah ok, i expected a slightly longer explenation why 32k−13^{2k-1} is an integer. (to me its obvious, just thought it)
– saturatedexpo
2 days ago

3j3^{j} is an integer when jj is nonnegative. Since k≥1k\geq 1, 2k−1≥12k-1 \geq 1
– Siong Thye Goh
2 days ago

When you are at 14a−32k−1⋅2+32k+114a-3^{2k-1}\cdot2+3^{2k+1} go on as follows:
14a−32k−1⋅2+32k+1=14a−32k−1⋅2+32k−1⋅32=14a−32k−1(2−9)=…
14a-3^{2k-1}\cdot2+3^{2k+1}=
14a-3^{2k-1}\cdot2+3^{2k-1}\cdot3^2=
14a-3^{2k-1}(2-9)=\dots