1. ## Remainders mod x

Question
Compute the remainder modulo 7 of $\displaystyle 2222^5555$

My notes do not make this explicit so I ask here. Is this question asking for a number x such that $\displaystyle x\equiv{2222^{5555}} (mod{ }n)$

If so, then this question is equivalent to solving the diophantine equation
$\displaystyle x-7k=2222^{55555}$
?
And I need to find the least positive integer x that satisfies this equation?
How shall I proceed to do this?

2. Originally Posted by I-Think
Question
Compute the remainder modulo 7 of $\displaystyle 2222^5555$

My notes do not make this explicit so I ask here. Is this question asking for a number x such that $\displaystyle x\equiv{2222^{5555}} (mod{ }n)$

If so, then this question is equivalent to solving the diophantine equation
$\displaystyle x-7k=2222^{55555}$
?
And I need to find the least positive integer x that satisfies this equation?
How shall I proceed to do this?

Reduce the base modulo 7: $\displaystyle 2222=3\!\!\pmod 7$ , so $\displaystyle 2222^{5555}=3^{5555}\!\!\pmod 7$

Now divide the power by 7 with remainder: $\displaystyle 5555=7\cdot 793+4$ , so $\displaystyle 3^{5555}=\left(3^{793}\right)^7\cdot 3^4$.

Use now Fermat's Little Theorem: $\displaystyle \forall n\in\mathbb{Z}\,,\,z^p=z\!\!\pmod p\,,\,\,p$ a prime , so that

$\displaystyle \left(3^{793}\right)^7=3^{793}\!\!\pmod 7$ . Repeat the above with 793 instead of 5555...(of course, keep track of $\displaystyle 3^4$ and all the small powers you'll get!)

Tonio