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?
 A: 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).
A: 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$.
