# Remainders mod x

• October 15th 2010, 10:34 PM
I-Think
Remainders mod x
Question
Compute the remainder modulo 7 of $2222^5555$

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

If so, then this question is equivalent to solving the diophantine equation
$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?
• October 15th 2010, 10:57 PM
tonio
Quote:

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

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

If so, then this question is equivalent to solving the diophantine equation
$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: $2222=3\!\!\pmod 7$ , so $2222^{5555}=3^{5555}\!\!\pmod 7$

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

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

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

Tonio