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

Question

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

Answer 1

\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}

Answer 2

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$.

Answer 3

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$.

Answer 4

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

Answer 5

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}$$

Answer 6

By Euler'sTheorem: \begin{align} 5^{55}+3^{55} &\equiv\frac 15+\frac 13\\ &\equiv\frac 8{15}\\ &\equiv 8\pmod{16} \end{align}

Answer 7

$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})$

Answer 8

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$.