5
$\begingroup$

$13^{11^{7^{5^{3^2}}}}\bmod100=37$, according to WolframAlpha. My calculations provided the same result, however upon consideration, I realized that they don't make sense, even though the result is correct. What I did was, starting from the top, I calculated every exponent $\bmod 100$. $3^2\equiv 9, 5^9\equiv25, 7^{25}\equiv 7, 11^7\equiv 71, 13^{71}\equiv37\bmod100$. But then I realized, I should have been taking everything $\bmod\phi(100)=40$. But why did this work anyway? Is it just luck? Also, is there a faster way than this?

$\endgroup$
6
$\begingroup$

As $\lambda(100)=20$

$$13^{11^{7^{5^{3^2}}}}\equiv13^{11^{7^{5^{3^2}}}\pmod{20}}\bmod100$$

Now $11^{2m+1}=11(1+10)^{2m}\equiv11(1)\pmod{20}$

Now $13^{11}=13(170-1)^5\equiv13(-1+5\cdot170)\pmod{100}\equiv50-13$

Here $2m+1={7^{5^{3^2}}}$

$\endgroup$
2
$\begingroup$

If you were to do this in your head, the first thing to note is that it's not the euler function, but rather the period that matters. For 100, this is 20. That is $100 \mid x^{20}-1$.

The way to find this out, is to take the lowest common multiple of the euler-function of each prime-power, so $ \mbox{lcm}(\phi(4), \phi(25)$. The reason for this can be seen in the period for 91 in decimal. Although $\phi(91)=72$, the cycles of 7 (ie $\phi(7)=6$ and 13 ($\phi(13)=12$) run side by side.

Useful to know is that 7 has 5 as a sevenite, that is, $5^2 \mid 7^{5-1}-1$.

This means we are looking first for ${11^x} \mbox{ for } x\pmod{20}$, and then ${7^x}\mbox{ for } x\pmod{4}$.

So ${5^x=1}\pmod{4}$ always

Then ${7^x=7}\pmod{20}$ when x=1, mod 4

Then ${11^7=71}\pmod{100}$, is easy to find on pascal's triangle.

Adding 13 to the mix presents no problem. 71 reduces to 11, modulo 20.

We then seek $13^{11}$. Note here that $13^2 = 1,7,-1$ base 10. Its tenth power is then $13^{10}=,,,5\times 7,-1$ or 49. We find then that 13*49=13*50-13, or 50-13, or 37.

Because 100 is divisible by its period-length, one can continue to use the tower of primes without further adjustments.

All done by mental arithmetic.

$\endgroup$
1
$\begingroup$

Always work from the bottom up - the top of the tower is quite likely to be irrelevant.

So, from the bottom, we're interested in the order of $13 \bmod 100$. The Carmichael function $\lambda$ is useful here; we know that the order of $13$ divides $\lambda(100)=20$. We could check to see if $13$ obviously has any lower order but we can also leave that for now.

So then we're interested in the order of $11 \bmod 20$. This is immediately apparent to be $2$, since $11^2=121 \equiv 1 \bmod 20$. In fact this is an example of a common pattern, $(2n\pm 1)^2\equiv 1 \bmod 4n$.

So now we just need to know if the exponent of the $11$ is odd or even. And it's some large power of $7$, so it's odd, and this gives us:

$$13^{11^{7^{5^{3^2}}}} \equiv 13^{11}\bmod 100$$

We can calculate this various ways, but exponentiation by squaring is not too onerous, especially since I can use the pattern of squares $\bmod 100$ that repeats at $50$.

$\bmod 100: \\ 13^2\equiv 69 \\ 13^4\equiv 69^2 \equiv 19^2 \equiv 61 \\ 13^5\equiv 61\cdot 13 \equiv 93 \equiv -7 \\ 13^{10} \equiv (-7)^2\equiv 49 \\ 13^{11} \equiv 49 \cdot 13 \equiv 37 $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.