Finding the remainder when $5^{55}+3^{55}$ is divided by $16$ 
Find the remainder when $5^{55}+3^{55}$ is divided by $16$.

What I try
$a^{n}+b^{n}$ is divided by $a+b$ when $n\in $ set of odd natural number.
So $5^{55}+3^{55}$ is divided by $5+3=8$
But did not know how to solve original problem
Help me please
 A: \begin{align}
5^{55}+3^{55}&\equiv(125\times625^{13})+(27\times81^{13})&&\pmod {16}\\
&\equiv 125\times 1+27\times 1&&\pmod{16}\\
&\equiv 8&&\pmod {16}\\
\end{align}
A: Notice that $5 = 4+1$ and $3=4-1$.  Then by the binomial theorem we have
$$5^{55}+3^{55} = (4+1)^{55}+(4-1)^{55} =$$
$$\sum_{k=0}^{55}  {55 \choose k}  4^{55-k}1^{k} + \sum_{k=0}^{55}  {55 \choose k}  4^{55-k}(-1)^{k}.$$
Now every term in sight has $4^2 = 16$ except the last two in each sum.  So the above equals
$$55(4) +1 + 55(4) -1 = 8(55) = 8(54) +8.$$
Since $8(54)$ is a multiple of $16$, the answer is $8$.
A: Let $a_n = 5^{n}+3^{n}$. Then $a_{n+2} = 8a_{n+1} -15 a_n$ because $5$ and $3$ are roots of $x^2=8x-15$. Mod $16$ we get
$$
2,8,2,8,\dots
$$
that is, the sequence is periodic of period $2$. This can be proved by induction. Therefore, $a_{55} \equiv a_1 = 8$.
A: Hint:
Use Carmichael Function, $\lambda(16)=4$ and as $-3\cdot5=-5\cdot3\equiv1\pmod{16}$
$$3^{55}=(3^4)^{14}3^{-1}\equiv1^{14}\cdot3^{-1}\pmod{16}\equiv-5$$
$$5^{55}=(5^4)^{14}3^{-1}\equiv1^{14}\cdot5^{-1}\pmod{16}\equiv-3$$
Alternatively, 
$$3^{2n+1}+5^{2n+1}=3^{2n+1}+(8-3)^{2n+1}\equiv\binom{2n+1}18^13^{2n}\pmod{16}\equiv8$$
as $\displaystyle\binom{2n+1}13^{2n}$ is odd 
A: Continuing your method:
$$5^{55}+3^{55}=(5+3)(5^{54}-5^{53}\cdot 3+5^{52}\cdot 3^2-\cdots +5^2\cdot 3^{52}-5\cdot 3^{53}+3^{54}) \Rightarrow \\
\small 5^{54}-5^{53}\cdot 3+5^{52}\cdot 3^2-\cdots +5^2\cdot 3^{52}-5\cdot 3^{53}+3^{54}\equiv 1-1+1-\cdots+1-1+1\equiv 1\pmod{2}$$
Hence:
$$5^{55}+3^{55}\equiv 8 \pmod{16}$$
A: By Euler'sTheorem:
\begin{align}
5^{55}+3^{55}
&\equiv\frac 15+\frac 13\\
&\equiv\frac 8{15}\\
&\equiv 8\pmod{16}
\end{align}
A: $3^4 = 81 = 16\cdot 5 + 1 \equiv 1 \mod(16)$
Then
$3^{52} = (3^{4})^{13} \equiv 1^{13} \mod(16) $
Then
$3^{55} = 3^3 \cdot 3^{52} \equiv 27 \cdot 1 \mod(16)$
And $27 \equiv 11 \mod(16)$
Thus 
$3^{55} \equiv 11 \mod(16)$
Now,
$5^2 \equiv 9 \mod(16)$
So $(5^2)^{26} \equiv (3^{2})^{26} \mod(16)$
Then
$5^{52} \equiv 3^{52} \mod(16)$
And as before, $3^{52} \equiv 1 \mod(16)$
Thus
$5^{52} \equiv 1 \mod(16)$
So
$5^{55} \equiv 5^{3} \mod(16)$
And $5^{3} = 125 = 16 \cdot 7 + 13$
Then $5^{55} \equiv 13 \mod(16)$
And thus $5^{55} + 3^{55}\equiv 13 + 11 \mod(16)$
$24 \equiv 8 \mod(16)$
Finally $5^{55} + 3^{55} \equiv 8 \mod(16)$
So $16 \not| (5^{55} + 3^{55})$
A: We can simplify the expression as follows: $5^{55} + 3^{55} \equiv (5^4)^{13}\cdot 5^3 + (3^4)^{13}\cdot 3^3 \pmod {16}\\
\equiv (9^2)^{13}\cdot 5^2\cdot 5 + 1^{13}\cdot 11\pmod {16}\\
\equiv 1^{13}\cdot9\cdot 5 + 11\pmod {16}\\
\equiv 8\pmod {16}$. 
So the remainder is $8$.
