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$

With congruences instead of induction:
(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$.
