# Prove some divisibility results by induction

Please hint me, I have two questions:

Prove by induction that:

1)

$${13}^n+7^n+19^n=39k,\,\, n\in\mathbb O$$

in which $\mathbb O$ is the set of odd natural numbers.

2)

$$5^{2n}+5^n+1=31t,~n\not=3k,$$ $n\in \mathbb N$

-
You may make the title more descriptive. –  Babak S. Oct 11 '13 at 10:42
Do you really need to prove the first by induction? Considering residues modulo $39$ is sufficient. –  Kieren MacMillan Oct 11 '13 at 10:45
what have you tried? –  Ma Ming Oct 11 '13 at 10:50
I need solve the both of them with induction but if you have another solution , please write it. I like different ways. –  Mohsen Oct 11 '13 at 11:01

(1) You need to show that $13^n+7^n+19^n$ is divisible by both $3$ and $13$. This follows from $$13^n+7^n+19^n\equiv 1^n+1^n+1^n=3\equiv 0 \ ({\rm mod\ } 3),$$ $$13^n+7^n+19^n\equiv 0^n+7^n+(-7)^n\ ({\rm mod\ }13),$$ where the last expression is $=0$ since $n$ is odd.

(2) Here, I'd like to rewrite $$5^{2n}+5^n+1=(5^n)^0+(5^n)^1+(5^n)^2={(5^n)^3-1\over 5^n-1}={5^{3n}-1\over 5^n-1},$$ using the formula for geometric series (assuming $n\neq 0$). Note that $$5^{3n}-1=125^n-1\equiv 1^n-1=0\ ({\rm mod\ }31).$$ If $n$ is not divisible by $3$ then $n=3k+1$ or $n=3k+2$, and we have $$5^{3k+1}-1=5\cdot 125^k-1\equiv 5\cdot 1^k-1=4\ ({\rm mod\ }31),$$ $$5^{3k+2}-1=25\cdot 125^k-1\equiv 25\cdot 1^k-1=24\ ({\rm mod\ }31)$$ So $31$ divides the product $(5^{2n}+5^n+1)(5^n-1)=5^{3n}-1$, but not the factor $5^n-1$. Since $31$ is a prime number, it has to divide the other factor $5^{2n}+5^n+1$.

-
The last method resembles math.stackexchange.com/questions/515618/… –  lab bhattacharjee Oct 11 '13 at 13:35
very nice solution ! excellent ! :) –  average Oct 11 '13 at 13:56
Well done!!!!!! –  Mohsen Oct 11 '13 at 17:13

In the first one, you have to make two inductions.

For $n=1, 13^1+7^1+19^1 = 39 = 39k$ for $k=1$

Assume the proposition is true for $n$, that is

$$13^n + 7^n + 19^n = 39k \qquad (1)$$ Let's check out what's gonna happen for $n+2$:

$$13^{n+2} + 7^{n+2} + 19 ^{n+2}$$ $$= 13^n * 169 + 7^n * 49 + 19^n * 361$$ $$= (39k-7^n - 19^n)*169 +7^n*49 + 19^n * 361 \qquad Got \,13^n from \,(1)$$ $$= 39k*169 + 192 * 19^n - 120 * 7^n$$ (2)

It's clear that $39k*169$ is divisible by 39, let's make another induction for $192 * 19^n - 120 * 7^n$

For $n=1: \qquad 192 * 19^1 - 120 * 7^1 = 72*39$

Asuume $192 * 19^n - 120 * 7^n = 39t \qquad (3)$ and check out the situation for $n+2$

$$192*19^{n+2} - 120*7^{n+2}$$ $$=192*361*19^n - 120 * 49 * 7^n$$ $$=361 * (39t +120 * 7^n) - 120 *49*7^n \qquad Again, got \, 192*19^n from \,(3)$$ $$=361 * 39t + 120*7^n * (361-49)$$ $$= 361*39t + 120*7^n*8*39 \qquad As\, 361-49=8*39$$ $$= 39* (361t - 120*7^n*8) \qquad (4)$$

Plug $(4)$ into $(2)$ to show $$13^{n+2} + 7^{n+2} + 19 ^{n+2}$$ is divisible by $39$. Induction is done. q.e.d.

And here comes the second one. It's the same with the first actually, just one induction.

For $n=1$ and $n=2$, the proposition is true. I'm not going to write the results. We can do the induction with iterations with $3$, as we have to show it for the $n\neq3k$.

Let's start. Assume for $n$ the proposition is true, that is $5^{2n} + 5^n +1 =31t$

Check for the situation for $n+3$:

$$5^{2(n+3)}+5^{n+3} + 1$$ $$= 5^{2n} * 15625 + 5^n * 125 + 1$$ $$= 5^{2n} * 15625 + 125 (31t - 5^{2n}-1) + 1 \qquad Got \,5^n \,from \,the \,second\, premise$$ $$= 5^{2n} * 15625 + 31*125 - 125* 5^2n - 124$$ $$= 5^{2n} (15625 - 125) + 31*125 - 4*31$$ $$= 5^{2n} * 31 * 500 + 31*125t - 4*31$$ $$= 31(5^{2n}*500 + 125t - 4 )$$ $$= 31*s$$

Induction is done. q.e.d.

-
Thanks very much. –  Mohsen Oct 11 '13 at 11:22
I've added the solution of the second one as well, in the edit. –  Zafer Sernikli Oct 11 '13 at 11:38

For one, let $\displaystyle f(n): 13^n+7^n+19^n=39k$ holds true for $n=m$ where $m$ is odd positive integer

$\implies\displaystyle13^m+7^m+19^m=39k_1$

$\implies\displaystyle13^m+7^m+19^m=13k_2\implies 7^m+19^m=13k_3\ \ \ \ (1)$

Now for $n=m+2,$

$\displaystyle13^{m+2}+7^{m+2}+19^{m+2}\equiv7^m\cdot49+19^m\cdot361\pmod{13}\equiv-3(7^m+19^m)\pmod{13}\equiv0$ [using $(1)$]

$\displaystyle13^{m+2}+7^{m+2}+19^{m+2}-(13^m+7^m+19^m)=13^m(13^2-1)+7^m(7^2-1)+19^m(19^2-1)\equiv0\pmod3$

$\displaystyle\implies 13^{m+2}+7^{m+2}+19^{m+2}\equiv13^m+7^m+19^m\pmod3\equiv0$

$\displaystyle\implies 13^{m+2}+7^{m+2}+19^{m+2}$ is divisible by lcm$(13,3)=39$ if $f(n)$ holds for $n=m$

Show that $f(n)$ holds if $n=1$

For two, let $g(n):5^{2n}+5^n+1=31t$ holds true for $n=m$

Now, $5^{2m}+5^m+1=(5^2)^m+5^m+1\equiv(-6)^m+5^m+1\pmod{31}$

$\displaystyle\implies (-6)^m+5^m+1$ is divisible by $31$

Now for $n=m+3,$

$\displaystyle (-6)^{m+3}+5^{m+3}+1-\{(-6)^m+5^m+1\}=(-6)^m\{(-6)^3-1\}+5^m(5^3-1)=(-6)^m(-217)+5^m(124)\equiv0\pmod{31}$

$\displaystyle\implies (-6)^{m+3}+5^{m+3}+1\equiv(-6)^m+5^m+1\pmod{31}\equiv0$

Now show that $g(n)$ holds for $n=1,2$

-