# 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

• Try expanding $(4+1)^{55}+(4-1)^{55}$. – almagest Dec 28 '19 at 16:13

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

• Whoever downvoted this answer yesterday, please be kind to comment and tell me what did you dislike, so that I can improve. – Martund May 9 at 5:48

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

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

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

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

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

• O.P would find an explanation even more constructive , so you could think about adding one. – The Demonix _ Hermit Dec 28 '19 at 17:30

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

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