Vtyjkyuk

Prove that $6n+n^7$ is divisible by $7$ for $n>0$.

Skip the $n=1$ part...

Induction hypothesis:
$P(k)=6k+k^7=k(6+k^6)$ is divisible by $7$

For $n=k+1$, we have that $$P(k+1)=6(k+1)+(k+1)^7=(k+1)[6+(k+1)^6]$$
How should I continue? Thanks

$$(k+1)^7=binom70+binom71k^1+binom72k^2+cdots+binom76k^6+binom77k^7$$

$$(k+1)^7=1+7k+binom72k^2+cdots+binom76k^6+k^7$$
$$P(k+1)=6(k+1)+(k+1)^7=6k+6+1+k^7+7(...)$$
$$P(k+1)=6(k+1)+(k+1)^7=6k+7+k^7+7(...)$$
$$P(k+1)=6(k+1)+(k+1)^7=(6k+k^7)+7+7(...)$$

$6k+k^7$ is already divisible by 7 as you assumed this, other remaining terms are also multiple of 7 thus divisible by 7

$$ forall nge 1 hspace10pt P(n) implies P(n+1)$$

As an alternative by FLT we have that

$$6n+n^7 equiv-n+nequiv 0 pmod 7$$

Since $binom7i$ is divisible by $7$ for $ine0,7$, we have that beginalignP(k+1)&=colorred6(k+1)+colorblue(k+1)^7\&=colorred6k+6+colorbluek^7+7(textsomething)+1\&=(6k+k^7)+7(textsomething+1)endalign which is divisible by $7$ from the induction hypothesis.

There are, in my opinion, two possible approaches.

The first one is to show it is true for $n=1, ldots , 7$ and then show by induction that if it's true for $n$ then it's true for $n+7$.

The second one is to use the Fermat's Little Theorem

Write
$$(n^7-n)+7n=frac(n-1)n(n+1)left((2n-1)^2+3right)left((2n+1)^2+3right)16+7n$$

If $7mid n$ we are done, if $7notmid n$ there are some possibilities:

• $n=7k+1Rightarrow 7mid n-1$


• $n=7k+2Rightarrow 7mid (2n+1)^2+3$


• $n=7k+3Rightarrow 7mid (2n-1)^2+3$


• $n=7k-3Rightarrow 7mid (2n+1)^2+3$


• $n=7k-2Rightarrow 7mid (2n-1)^3+3$


• $n=7k-1Rightarrow 7mid n+1$

We don't have to worry about $16=2^4$ in the denominator, since $gcd(2,7)=1$, and both:

• $4mid (2n-1)^2+3$


• $4mid (2n+1)^2+3$

are true.

Alt. hint:  the product of $7$ consecutive numbers is always divisible by $7$, so:

$$
beginalign
7;mid; (n-3)(n-2)(n-1)n(n+1)(n+2)(n+3) &= n^7 - 14 n^5 + 49 n^3 - 36 n \
&= n^7+6n -left(14n^5-49n^3+42nright) \
&= n^7+6n - 7left(2n^5-7n^3+6nright)
endalign
$$