# A “fast” approach to solve $2^{133} \equiv x \mod 133$

I have to solve this equation $2^{133} \equiv x \mod 133$.Using Euler's theorem I reduced it to $2^{25} \equiv x \mod 133$ but I couldn't think off any fast way to proceed after this.

Any ideas?

-
Do it mod 7 and mod 19, then use Chinese remainder theorem. – Soarer Sep 15 '11 at 1:46
$2^{25}=2(2^{3\cdot 8})=2((8^2)^2)^2$. If you compute by doing repeated squaring and reduce mod 133 every time you square, the numbers you work with won't be too big. – Aaron Sep 15 '11 at 1:51
And even the original $2^{133}$ is $2^{2^7}\times 2^5$, which can be done in less than ten modular multiplications. – Henning Makholm Sep 15 '11 at 1:58
@Foolmath: I don't understand your point. Do $x \equiv a$ and $a \equiv x$ feel different to you? – Soarer Sep 15 '11 at 2:05
@Soarer:I get your point,but using CRT isn't really fast approach for this problem I guess. – Quixotic Sep 15 '11 at 2:38

## 2 Answers

HINT $\$ for primes $\rm\: p\ne q,\ \ p\!-\!1\ |\ q\!-\!1\ \Rightarrow\ c^{q}\equiv\: c\pmod{p\:q}\$ by Fermat's little Theorem.

So for $\rm\:p,q = 7,19,\ c = 2^7\:$ we infer that $\rm\: 2^{\:7\:\cdot\: 19}\equiv 2^7\equiv 128 \equiv {-}5 \pmod{7\cdot 19}\ \$ QED

Proof $\$ Assume $\rm\ p \ne q\$ are primes and $\rm\: q = 1 + k\:(p-1)\:,\ k\in \mathbb N\:.\:$ By Fermat's little Theorem $\rm\:mod\ q\!:\ c^q = c\:;\ \ \ mod\ p\!:\ c^q =\: c^{\:1+k\:(p-1)} =\: c\ (c^{\:p-1})^{k}\equiv\: c\$ if $\rm\:c\not\equiv\: 0\:,\:$ and $\rm\:c^q\equiv c\:$ if $\rm\:c\equiv 0\:.\:$
Therefore $\rm\:p,q\ |\ c^q-c\:$ $\:\Rightarrow\:$ $\rm\:lcm(p,q) =\: p\:q\ |\ c^q-c\:.\ \$ QED

NOTE $\$ The above proposition is a special case of a general Fermat-Euler-Carmichael Theorem.

Note that this is yet another example of constant case optimization of Chinese Remainder (CRT).

-
what is odd primes?I didn't understand your approach at all :/ – Quixotic Sep 15 '11 at 3:38
@FoolForMath: Odd primes means primes that are odd, i.e., bigger than 2. For the first implication: To see that $p | 2^{pq} - 2^p$, apply Fermat's Little Theorem (FLT) for $p$ twice, using the condition $p-1 | q-1$. To see that $q | 2^{pq} - 2^p$, apply FLT for $q$. – Ted Sep 15 '11 at 3:55
@Foo I've appended a complete proof below the hint. – Bill Dubuque Sep 15 '11 at 4:38

Use $133 = 7 \times 19$. Use $2^p = 2 \mod p$ for $p \in \mathbb{P}$.

Now $2^{133} = (2^7)^{19} \mod 7 = 2^{19} \mod 7 = (2^7)^2 \times 2^5 = 2^2 \times 2^5 = 2^7 = 2 \mod 7$. Similarly $2^{133} = (2^{19})^7 = 2^7 = 14 \mod 19$. Thus

Let $x = 2^{133} \mod 133$, then from $x = 14 \mod 19$, it follows that $x = 14 + 19 \times k$. From $x = 2 \mod 7$, it follows $(14 + 19 \times k) = 5 \times k = 2 \mod 7$, and $k = 6 \mod 7$. From this I get $2^{133} = 128 \mod 133$.

-
+1,I understood this approach,for the last part I used CRT,however not much a fast way I guess. – Quixotic Sep 15 '11 at 2:28