modular exponentiation $2^{103}\equiv 63\pmod {143}$ I am trying to prove that $2^{103}\equiv 63\pmod {143}$.One way is to ''break'' the power of $2$ but $103$ is prime.Is there any way or theorem?
 A: One very common method for calculating large powers is repeated squaring.
To use it for your example here, we have:
$$
2 \equiv 2 \pmod{143} \\
2^2 \equiv 4 \pmod{143} \\
2^4 \equiv 16 \pmod{143} \\
2^8 \equiv 256 \equiv 113 \pmod{143} \\
2^{16} \equiv (-30)^2 \equiv 900 \equiv 42 \pmod{143} \\
2^{32} \equiv 42^2 \equiv 1764 \equiv 48 \pmod{143} \\
2^{64} \equiv 48^2 \equiv 2304 \equiv 16 \pmod{143} \\
$$
We therefore have:
$$
\begin{align}
2^{103} &\equiv 2^{64} \cdot 2^{32} \cdot  2^4 \cdot 2^2 \cdot 2 \pmod{143} \\
&\equiv (16 \cdot 48) \cdot 16 \cdot 4 \cdot 2 \pmod{143} \\
&\equiv (53 \cdot 16) \cdot (4 \cdot 2) \pmod{143} \\
&\equiv 133 \cdot 8 \pmod{143} \\
&\equiv 63 \pmod{143}
\end{align}
$$
A: You can still "break" it up: Rewrite $2^{103}$ as $2^{100}\cdot 2^3$, then break up the power $2^{100}$ into whatever pieces you like. For example:
$2^{103}=2^{100}\cdot 2^3=(2^{10})^{10}\cdot 8\equiv (23)^{10}\cdot 8=(23^2)^5\cdot 8\equiv (100)^5\cdot 8\equiv 133\cdot 133\cdot 85\equiv 100\cdot 85\equiv 63$.
A: It doesn't matter that much the $103$ is prime, that just means we'll have a final factor that's different from the rest. What makes a straight forward calculation upleasant is the $143$ and that fact that the smallest power of $2$ that has a really small remainder modulo $143$ is $2^{28}$. Andre's hint in the comments is the way to go.
A: Here is a solution that does not make use of Fermat's Little Theorem.

The Algorithm:


*

*Input: $x=2,e=103,n=143$

*Output: $y=1$

*Repeat until $e=0$:


*

*If $e\equiv1\pmod2$ then set $y=yx\bmod{n}$

*Set $x=x^2\bmod{n}$

*Set $e=\left\lfloor\frac{e}{2}\right\rfloor$
C Implementation:
int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(2,103,143); // 63

Intermediate Output:
   x   |   e   |   y
-------|-------|-------
    2  |  103  |  143
    4  |   51  |    2
   16  |   25  |    8
  113  |   12  |  128
   42  |    6  |  128
   48  |    3  |  128
   16  |    1  |  128
  113  |    0  |   63


Please note that the complexity is $O(\log_2e)$, resulting in $\lceil\log_2103\rceil=7$ iterations.
