7
$\begingroup$

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

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

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

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

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.