Calculate $2^{48} \equiv x \mod 140$

Question

I've calculated the following equation and I've got this:

Does there exist an easier solution?

Answer 1

It seems that you have obtained the exponent as $48=\varphi(140)$.

We could use Euler's theorem in combination with Chinese remainder theorem.

Namely we have $$2^{\varphi(35)}\equiv 1 \pmod{35}$$ by Fermat's theorem. Consequently, we also have $2^{\varphi(140)}\equiv 1 \pmod{35}$. It is clear that $4\mid 2^{48}$, hence $2^{\varphi{140}}\equiv 0 \pmod4$.

The system of congruences \begin{align*} 2^{\varphi(140)}&\equiv 1 \pmod{35}\\ 2^{\varphi(140)}&\equiv 0 \pmod{4} \end{align*} has a unique solution modulo $4\cdot 35=140$. It is not difficult to find that it is $$2^{\varphi(140)}\equiv 36 \pmod{140},$$ since we only have four possibilities $1$, $36$, $71$ and $106$ fulfilling the first congruence.

Answer 2

$2^{48} = (2^8)^6 = 256^6 \equiv(-24)^6 = 576^3 \equiv 16^3 = 4096 \equiv 36 \pmod {140}$

Answer 3

$2^{48} \equiv 0 \bmod 4$

$2^{48} = (2^2)^{24} \equiv (-1)^{24} \equiv 1 \bmod 5$

$2^{48} = (2^3)^{16} \equiv (1)^{24} \equiv 1 \bmod 7$

So $2^{48} \bmod 140$ must be a multiple of $4$ of the form $1+35k$. We get $36$ for $k=1$.