0
$\begingroup$

I'am looking for the remainder produced when the integer $2099^{2017^{13164589}}$ is divided by $99$ ? The goal reached is to avoid large integers.

$\endgroup$
1
  • $\begingroup$ Welcome to MSE! Please share your thoughts so people can help you better. $\endgroup$
    – KittyL
    Feb 2, 2016 at 20:46

2 Answers 2

5
$\begingroup$

We know by Euler's Totient Function that $a^{\phi(99)}\equiv 1\mod 99$ for all $a$ with $\gcd(a,99)=1$ (so also for $a=2099$). So, the exponent works $\mod \phi(99)$, and $\phi(99)=60$, so we wish to compute $$2017^{13164589}\mod 60$$ We can again use the totient function to know that $a^{\phi(60)}\equiv a^{16}\equiv 1\mod 60$ - thus, we wish to compute $$13164589\mod 16$$ This is not too hard: this is $13$. Now we know $$2017^{13164589}\equiv 2017^{13}\equiv 37^{13}\mod 60$$ A little bit of trying and we see $37^4\equiv 1 \mod 60$ - giving us $$2017^{13164589}\equiv 37\mod 60$$ Thus we're left with $$2099^{2017^{13164589}}\equiv 2099^{37}\equiv 20^{37}\mod 99$$ This requires a bit of brute force to obtain $$2099^{2017^{13164589}}\equiv 92\mod 99$$ Still a computationally-heavy solution, but better than simply computing $2099^{2017^{13164589}}$.

Hope this helped!

$\endgroup$
2
  • 1
    $\begingroup$ If one works separately mod $9$ and mod $11$, the calculations can be done in one's head. $\endgroup$ Feb 2, 2016 at 19:34
  • 1
    $\begingroup$ Same principles as in the nicely written answer above that works mod $99$. For example, $2099\equiv 2\pmod{9}$ and $2017\equiv 1\pmod{6}$ so the whole ugly exponent is congruent to $1$ mod $6$, and therefore our number is congruent to $2$ mod $9$. Mod $11$ is a little more work, but not much. $\endgroup$ Feb 2, 2016 at 19:42
1
$\begingroup$

We'll use the fact $a^k\equiv a^{k\mod\phi(n)}\mod n$ where $\phi$ is Euler's totient function. This congruence follows from $a^{\phi(n)}\equiv 1\mod n$.

$\phi(9)=6$ and $\phi(6)=2$. $$ 2017^{13164589}\equiv2017^{13164589\mod\phi(6)}\equiv2017^{13164589\mod 2}\equiv 2017^1\equiv1\mod 6\\ 2099^{2017^{13164589}}\equiv2099^{2017^{13164589}\mod \phi(9)}\equiv2099^{2017^{13164589}\mod 6}\equiv2099^1\equiv2\mod 9 $$ $\phi(11)=10$ and $\phi(10)=4$. $$ 2017^{13164589}\equiv2017^{13164589\mod 4}\equiv 2017^{9\mod 4}\equiv2017^1\equiv 7\mod 10\\ 2099^{2017^{13164589}}\equiv2099^{2017^{13164589}\mod 10}\equiv2099^7\equiv9^7\equiv(-2)^7\equiv-128\equiv-7\equiv4\mod 11 $$ Now consider the set of congruences $$ x\equiv2\mod 9,\quad x\equiv4\mod 11\cdots(1) $$ $x=9a+11b$ for some $a,b$. $(a,b)=(9,1)$ makes sure the previous congruences in $(1)$ are satisfied. So one solution to $(1)$ is $92$. As $gcd(9,11)=1$, by Chinese Remainder theorem $$ 2099^{2017^{13164589}}\equiv 92\mod(9\cdot11=99) $$ as $2099^{2017^{13164589}}$ is also a solution to $(1)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .