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

Question

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?

Changing "divisible" to "divided" would make this extremely unorganized question a lot clearer (though still unorganized). — barak manos, Oct 01 '14 at 08:10
You can see it by taking examples. Suppose if any of $a,b,c,d,e$ is divisible by $f$, then clearly the whole expression $abcde$ is also dividible by $f$ — AgentS, Oct 01 '14 at 08:22

barak manos · Accepted Answer · 2014-10-01T10:16:52.880

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

1 Answers1