What is the remainder when ${2222}^{5555}+{5555}^{2222}$ is divided by $7$?

678 Views Asked by At

The question is multiple-choice.

What is the fastest approach to solve it?

One suggested solution is:

  • It can be seen that $[2222\equiv3\pmod7]\wedge[5555\equiv4\pmod7]$

  • Therefore $({2222}^{5555}+{5555}^{2222})\bmod7=({3}^{5555}+{4}^{2222})\bmod7$

  • Now it can be seen that $[3^3\equiv-1\pmod7]\wedge[4^3\equiv+1\pmod7]$

  • So we can rewrite it as ${(3^3)}^{1851}\cdot3^2+{(4^3)}^{740}\cdot4^2\equiv(-1\cdot9+1\cdot16)\equiv7\equiv0\pmod7$

Is it the right approach?

Will it work in every case?

I guess that the solution is assuming:

$$({a}\cdot{b}\cdot{c}\cdot{d}\cdot{e})\bmod{f}=({a}\bmod{f})\cdot({ab}\bmod{f})\cdot({ac}\bmod{f})\cdot({d}\bmod{f})\cdot({e}\bmod{f})$$

Is this assumption correct?

1

There are 1 best solutions below

0
On BEST ANSWER

First of all, since it's a multiple-choice question, the fastest approach depends on the choices.

For example, if all choices except for one are not between $0$ and $6$, then the answer is obvious.

That being said, there is one step in your solution which you could probably complete faster:

You had to do some math in order to conclude $[3^3\equiv-1\pmod7]\wedge[4^3\equiv+1\pmod7]$.

Without any computation, we know that $[3^6\equiv1\pmod7]\wedge[4^6\equiv1\pmod7]$.

This is due to the fact that $\forall{p}\in\mathbb{P}:[{0<n<p}\implies{n^{p-1}}\equiv1\pmod{p}]$.

Hence ${(3^6)}^{925}\cdot3^5+{(4^6)}^{370}\cdot4^2\equiv1\cdot243+1\cdot16\equiv259\equiv0\pmod7$.