Proof question: Prove that 2^(odd integer) + 5^(odd integer) + 2 is a multiple of 3, and 4^(any integer) + 1 can be expressed as 5n, 5n + 1 or 5n + 2. I had been working on the claim in the above question for sometime now. Statistically speaking, it works. For example:
$$\left(2^1 \right)+\left(5^1\right)+2=9,\\
\left(2^3\right)+\left(5^1\right)+2=15,\\ \ldots$$
It works with all the integers that I tested with. Can we give a simple proof for this one?
The second part is like this:
$$\left(4^1\right)+1=5,$$
$$\left(4^2\right)+1=17 = 15+2,$$
$$\left(4^3\right)+1=65,$$
$$\left(4^4\right)+1=257 = 255+2,\\ \ldots$$
So, the numbers are all expressed as $5n$, $5n+1$ or $5n+2$. Is there a generalised proof for this observation?
Thanks.
 A: HINT:
$2\equiv-1\pmod3\implies2^n\equiv(-1)^n$  (see $\#10$ property here)
and similarly for $5\equiv-1\pmod3$ 
and for $4\equiv-1\pmod5$
A: Anyone who has studied the $3x + 1$ problem with any degree of detail is aware of this property of numbers of the form $2^n$: either $2^n - 1$ is a multiple of $3$, or $2^n + 1$ is.
Obviously, $2^n$ itself can't be a multiple of $3$ (as long as $n$ is an integer). If $2^n = 3m - 1$, then $2^{n + 1} = (3 - 1)(3m - 1) = 9m - 3 - 3m + 1 = 3k + 1$, where $k = 2m - 1$.
But if $2^n = 3m + 1$, then $2^{n + 1} = (3 - 1)(3m + 1) = 9m + 3 - 3m - 1 = 3k - 1$, where $k = 2m + 1$.
So the powers of $2$ alternate this relationship with multiples of $3$, and since $1$ is odd in $2^1 = 2 = 3 - 1$ and $2$ is even in $2^2 = 4 = 3 + 1$, it follows that all odd-indexed powers of $2$ are one less than a multiple of $3$ and all even-indexed powers of $2$ are one more than a multiple of $3$. In the notation of congruences, we have $2^n \equiv 2 \pmod 3$ if $n$ is odd and $2^n \equiv 1 \pmod 3$ if $n$ is even.
Since $5 \equiv 2 \pmod 3$, we can pretty much repeat the same steps to show that the powers of $5$ also alternate this relationship to $3$ with the same correspondence between odd and even $n$. So if $m$ and $n$ are both odd integers, then $2^m + 5^n + 2 \equiv 2 + 2 + 2 = 6 \equiv 0 \pmod 3$.
The case of $4^n + 1$ is very similar and you should be able to figure out along similar lines.
A: For questions of divisibility, it helps to think in terms of modular arithmetic. 
To show something is a multiple of $3$, we can check to see if it is $0 \pmod 3$:
$$2^{2m+1} + 5^{2n+1} + 2 \equiv -1 + 2 + 2 \pmod 3 \equiv 3 \pmod 3 \equiv 0 \pmod 3$$
Note: $5$ raised to any power always ends in $5$, and $5 \equiv 2 \pmod 3$. As well, $2 \equiv -1 \pmod 3$ and $-1$ raised to an odd power is always $-1$.
