A number theory problem by Dibyojyoti Bhattacharjee

Given that:

$\begin{aligned} 2^{3n}-7n - 1 & = 8^n - 7n - 1 \\ & = (7+1)^n - 7n - 1 \\ & = \sum_{k=0}^n \binom nk 7^k - 7n - 1 \\ & = \sum_{k=2}^n \binom nk 7^k \\ & = 49 \sum_{k=0}^{n-2} \binom n{k+2} 7^k \end{aligned}$

Therefore $2^{3n} - 7n - 1 \bmod 49 = \boxed 0$ .

This is equivalent to proving that the $8^n - 7n - 1$ is always divisible by 49 for all positive integer $n$ . And we can prove this via mathematical induction .

Base step: This is trivially true for $n = 0$ , $8^1 - 7\cdot 1 - 1 = 0$ is divisible by 49.

Inductive step: We assume $n=k$ is true for some positive integer $k$ , then $8^k - 7k - 1$ is divisible by 49.

Inductive hypothesis: Let us prove that this holds for $n=k+1$ as well.

When $n=k+1$ , $8^{k+1} - 7(k+1) - 1 = 8 (8^k) - 7k - 8 = 7(8^k) + (8^k - 7k - 1) - 7 = 7(8^k - 1) + (\underbrace{8^k - 7k - 1}_{\text{divisible by 49}})$

Because $8^k - 1 = (7+1)^k - 1 = 7^k + k \cdot 7^{k-1} + \cdots$ is divisible by 7, then $7(8^k-1)$ must be divisible by $7^2=49$ . And thus, the entire expression above must be divisible by 49 as well.

Hence, by principles of mathematical induction, $8^n - 7n - 1$ is always divisible by 49 for all positive integer $n$ .

The answer to this problem is $\boxed0$ .

---

Addendum:

Mark Hennings made an excellent point:

Because $\big(8^{n+1}-7(n+1)-1\big) - 8\big(8^n - 7n - 1\big) = 49n,$ and the inductive step tells us that the latter bracket is divisible by 49, so former bracket is divisible by 49 too, and thus, $n=k+1$ is true as well.

Look at my solution:

There is also another way, let me wait, which one of you tell that?. I am very eager to see that.

since the question indicates the answer is the same for all "n", i just used n=1.
-> 8-7-1 = 0