3

So basically I figured out that this problem comes down to the following: We want to find the answer to $11^{(345^{678})} \ \text{mod} \ 13$. Then, because $11$ and $13$ are coprime, we know that $11^{\phi(13)} = 1 \ \text{mod} \ 13$. Because 13 is prime, we know that $\phi(13) = 12$. So $11^{12x} = 1 \ \text{mod} \ 13 $ for any integer x.

Then we need to find how many times 12 fits into $345^{678}$, so $345^{678} \ \text{mod} \ 12 $. However, $345$ and $12$ are not coprime, so we can't use Euler's theorem. This is the part where I don't actually know what to do anymore.

I tried the following: 345 mod 12 = 9 mod 12, so $345^{678} \ \text{mod} \ 12 = 9^{678} \ \text{mod} \ 12$. We know that $9^2 \ \text{mod} \ 12 = 81 \ \text{mod} \ 12 = 9 \ \text{mod} \ 12$. And we know that $9^4 \ \text{mod} \ 12 = 9^2 \cdot 9^2 \ \text{mod} \ 12 = 9 \ \text{mod} \ 12$. So $9^2$, $9^4$, $9^8$, $9^{16}$, $9^{32}$, $9^{64}$,$9^{128}$, $9^{256}$ and $9^{512}$ are all 9 in mod 12.

So then, $9^{678} \ \text{mod} \ 12 = 9^{512} \cdot 9^{128} \cdot 9^{32} \cdot 9^{4} \cdot 9^2 \ \text{mod} \ 12 = 9^5 \ \text{mod} \ 12 = 9 \ \text{mod} \ 12 $.

Then, going back to the original question, we know that we need to calculate $11^{9} \ \text{mod} \ 13 = 11^8 \cdot 11 \ \text{mod} \ 13$. Using the same trick as with the 9, I get that $11^{9} \ \text{mod} \ 13 = 8 \ \text{mod} \ 13$.

Is this correct? If not, what am I doing wrong? Is there a better way to attack such problems?

Thanks for reading,

K.

ArianJ
  • 670
  • 5
  • 21
  • It is correct, but, in order to prove that $9^{678}\equiv9\pmod{12}$ you could use the Fermat-Euler theorem. – José Carlos Santos Jun 04 '17 at 10:12
  • @JoséCarlosSantos Don't 9 and 12 need to be coprime in order to use the Fermat-Euler theorem? – ArianJ Jun 04 '17 at 10:14
  • Indeed. Sorry about that. But it is trivial that $9^{678}\equiv0\pmod3$ and you can use the Fermat-Euler theorem to prove that $9^{678}\equiv1\pmod4$. It follows from these two facts that $9^{678}\equiv9\pmod{12}$. – José Carlos Santos Jun 04 '17 at 10:20
  • @JoséCarlosSantos How does it follow from the fact that $9^{678} = 0 \ \text{mod} \ 3$ and $9^{678} = 1 \ \text{mod} \ 4$ that $9^{678} = 9 \ \text{mod} \ 12$? Is this the Chinese remainder theorem? – ArianJ Jun 04 '17 at 10:23
  • No. If $a\equiv0\pmod3$, then $a\equiv0\pmod{12}$, $a\equiv3\pmod{12}$, $a\equiv5\pmod{12}$, or $a\equiv9\pmod{12}$. Among these four possibilities, the only one for which is true thar $a\equiv1\pmod4$ is the $4^\text{th}$ one. – José Carlos Santos Jun 04 '17 at 11:06

2 Answers2

3

Your answer is correct, bur finding the value of $345^{678}\bmod 12$ is too long: as you observe, it is $9^{678}\bmod 12$. You missed that since $9^2\equiv9\mod13$, we also have (easy induction) $9^n\equiv 9\mod13$ for all $n\ge1$, so $$11^{345^{678}}\equiv (-2)^9=(-2)^6(-2)^3\equiv (-1)\cdot(-8)=8.$$

Bernard
  • 175,478
0

As $11\equiv-2\pmod{13},$

$11^{(345^{678})}\equiv(-2)^{(345^{678})}\pmod{13}$

Now $(-2)^6\equiv-1\pmod{13}\implies(-2)^{12}\equiv1,$

and $(-2)^{(345^{678})}\equiv(-2)^{(345^{678}\pmod{12})}\pmod{13}$

Now as $345\equiv0\pmod3\implies345^{678}\equiv0\ \ \ \ (1)$

and $345\equiv1\pmod4\implies345^{678}\equiv1\ \ \ \ (2)$

Using $(1),(2)$ by observation, $345^{678}\equiv9\pmod{12}$

$(-2)^{(345^{678}\pmod{12})}\equiv(-2)^9\pmod{13}\equiv?$

lab bhattacharjee
  • 274,582