1
$\begingroup$

How do I go about finding the solution to the following equation:

$a^{(b^c)} \equiv x \;(\bmod\; n)$

(assume $n$ does not divide $a$ for the purposes of using fermats little theorem)

Assume a and b can be somewhat small values around 5 to 100 and c can take values 1,000 to 10,000. What is the general algorithm for solving for $x$ using pen and paper?

I find this question pretty confusing because of the 3 exponents. I can solve regular problems of the type $a^{b} \equiv x \;(\bmod\; n)$ but I must be missing something with this one.

Example problems:

$2^{(6^{2015})} \equiv x \;(\bmod\; 19)$ - find $x$

$2^{(6^{2015})} \equiv y \;(\bmod\; 23)$ - find $y$ - really need help with this one

$\endgroup$
9
  • $\begingroup$ You already have isolated $x$ and $y$ terms, aren't you? $\endgroup$
    – Bumblebee
    Commented May 29, 2018 at 16:18
  • $\begingroup$ @Bumblebee Sorry I don't understand what you mean? $\endgroup$
    – Quaz
    Commented May 29, 2018 at 16:20
  • $\begingroup$ So, $2^{n}\equiv x\pmod{19}$ will depend on what the exponent $n$ happens to be mod $19-1$ (even in the case that $n$ happens to be of the form $b^c$). So to simplify $2^{6^{2015}}\pmod{19}$ you'll want to first simplify $6^{2015}\pmod{18}$. For that, it helps to notice that $6\cdot 6 = 2\cdot 18$. It is just going to be repeated applications of fermats and/or chinese remainder or other similar techniques. $\endgroup$
    – JMoravitz
    Commented May 29, 2018 at 16:22
  • $\begingroup$ @JMoravitz Okay, so $6^2 = 36 = 2*18$ then we get that $2^{2*18*6^{2013}} = 2^{{(2*18)}^{6^{2013}}} = 2^{{18}^{{2}^{{6}^{2013}}}}$ but we know that 2^{18} is congruent to 1 so we just get 1 as the answer? Can you confirm if my steps here are correct? $\endgroup$
    – Quaz
    Commented May 29, 2018 at 16:30
  • $\begingroup$ Once you add appropriate parentheses remembering that $a^{b^c}=a^{(b^c)}\neq (a^b)^c$, yes the result of the first will indeed be $1$. The second is done similarly except notice that $6$ has $2$ as a factor but does not have $11$ as a factor, affecting how we look at $6^n\pmod{22}$. You'll want to look at the two problems of $6^n\pmod{2}$ and $6^n\pmod{11}$ separately. $\endgroup$
    – JMoravitz
    Commented May 29, 2018 at 16:36

1 Answer 1

Reset to default
0
$\begingroup$

$23$ is prime so $2^{22} \equiv 1 \mod 23$

So $2^{6^{2015}} \equiv 2^k \mod 23$ where $6^{2015} \equiv k \mod 22$ so we must solve $6^{2015}\equiv k \mod 22$.

Use Chinese remainder theorem. $22 = 2*11$

$6^{2015} \equiv 6^5 \mod 11$ so $6^5 = 36*36*6\equiv 3*3*6 \equiv 54 \equiv -1 \mod 11$ and $6^{2015} \equiv 0 \mod 2$.

So $6^{2015} \equiv 10 \mod 22$.

So $2^{6^{2015}} \equiv 2^{10} \equiv 1024\equiv 12 \mod 23$.

====

I'm not familiar with the Chinese Remainder theorem, does it mean that I can simply split it into two separate questions of the two factors 2 and 11, do I just add the results then? And also.. how do I get the first part where you switch to mod 22 to solve for k?

Okay, Details.

By FLT $2^{22} \equiv 1 \mod 23$

So if $6^{2015} = 22m + r$ then $2^{5^{2015}}\equiv 2^{22m + r} \equiv (2^{22})^m*2^k \equiv 1*2^k \equiv 2^r \mod 23$.

So we must solve $6^{2015} = 22m + r$ or in other words we must solve $6^{2015} \equiv r \mod 22$.

Question 1: What is $6^{2015} \equiv r \mod 22$.

Now we can't use FLT because $6$ and $22$ are not relatively prime.

But we can use the Chinese remainder theorem that says.

If $n,m$ are relatively prime and if $x \equiv a \mod n$ and $x \equiv b \mod m$ then there is a unique solution to $x \mod nm$.

So $22 = 2*11$ and $\gcd (2,11) = 1$.

So if $x \equiv 6^{2015}\equiv 0 \mod 2$

and $x \equiv 6^{2015} \equiv (6^{10})^{201}*6^5 \equiv 6^5\equiv 10 \mod 11$

Then there will be a unique solution $6^{2015}\equiv x \mod 22$.

Now $0 \equiv 10 \mod 2$ and $10 \equiv 10 \mod 11$. And $10 \equiv 10 \mod 22$. so $x \equiv 10 \mod 22$ is a solution to $x\equiv 0 \mod 10$ and $x\equiv 10 \mod 11$. And by the chinese remainder theorem it is a unique solution.

So $6^{2015}\equiv 10 \mod 22$.

So $6^{2015} = 22m + 10$.

So $2^{6^{2015}} = 2^{22m + 10} \equiv (2^{22})^{m}*2^{10} \equiv 2^{10}\equiv 1024\equiv 12 \mod 23$.

=====

Okay, without CRT. We still need to find $6^{2015} \mod 22$.

$6^2 = 36 \equiv 14\equiv -8\mod 22$

$6^3 \equiv -8*6 \equiv -48 = -4 \mod 22$.

$6^4 \equiv -24 \equiv -2 \mod 22$

$6^5 \equiv -12 \equiv 10 \mod 22$

$6^6 \equiv 60 \equiv -6 \mod 22$

So $6^{2015} \equiv 6^{6*335+5}\equiv (-6)^{335}*6^{5}$

$\equiv (-6)^{6* 55+ 5}*10$

$\equiv (-6)^{55}*(-10)*10$

$ \equiv (-6)^{6*9 + 1}*(-100)$

$\equiv (-6)^9*(600)$

$\equiv (-6)^{6+3}* 6$

$\equiv (-6)*(-6)^3*6$

$\equiv 6^5 \equiv 10 \mod 22$.

$\endgroup$
4
  • $\begingroup$ I'm not familiar with the Chinese Remainder theorem, does it mean that I can simply split it into two separate questions of the two factors 2 and 11, do I just add the results then? And also.. how do I get the first part where you switch to mod 22 to solve for k? $\endgroup$
    – Quaz
    Commented May 29, 2018 at 18:35
  • $\begingroup$ If you are not familiar with the CRT you will have to study. No, you can not add the results. But if $\gcd(n,m) = 1$ and $x \equiv k \mod n$ and $x \equiv j \mod m$ the chinese remainder th. will say there is a unique solution to $x \mod nm$. As $10\equiv 0 \mod 2$ and $10 \equiv -1 \mod 11$ and $10 \equiv 10 \mod 22$ I know that if $x \equiv 0 \mod 2$ and $x \equiv -1 \mod 11$ that there has to be a unique solution $mod 22$ and as $10$ is a solution... that is it. $\endgroup$
    – fleablood
    Commented May 29, 2018 at 18:49
  • $\begingroup$ I see, thanks. Well we did not learn CRT in our class so I assume we are supposed to do it without it. I'll look into and learn it as it's been mentioned a few times but are you sure it's not possible without using CRT? $\endgroup$
    – Quaz
    Commented May 29, 2018 at 18:57
  • $\begingroup$ @fleabood Hey thanks I aced my finals thanks to you. $\endgroup$
    – Quaz
    Commented May 30, 2018 at 17:58

You must log in to answer this question.

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