Find the least positive residue of $40^{128} \mod 49$

Question

Looking for a way to find the least positive residue of $40^{128}\mod 49$ without a calculator. To also use the same technique for $2^{2015} \mod 31$.

What I've done so far is use Euler's totient function with Euler's theorem to narrow it down.

So $\phi(49) = \phi(7^2) = 7^2 - 7 = 42$ and since $\gcd(40,49) = 1$ by Euler's theorem, we have $40^{42} \equiv 1\mod 49$.

So $40^{128} = (40^{42})^3 \cdot 40^2 \equiv 1^3\cdot40^2 \equiv 40^2\mod49$

But from here, I don't know how to simplify this further without just plugging it in somewhere.

Answer 1

Right so $40^{42} \equiv 1 \mod 49$ so $40^{128}\equiv 40^2 \equiv (-9)^2 \equiv 81 \equiv 32 \mod 49$

Answer 2

$$40^2 \equiv (-9)^2 \equiv 81 \equiv 98 -17 \equiv 49-17 \equiv 32 \pmod{49} $$

Answer 3

$$40^{128}\equiv40^{128\bmod 42}= 40^2\equiv (-9)^2=81\equiv 32\mod 49.$$

Answer 4

Notice that $$128=4\times 8 \times 4 $$

$$40=49-9$$

$$(-9)^4 = (134)(49)-5$$

$$(-5)^8=(7972)(49)-3$$ $$(-3)^4=49+32$$ Thus the answer is $$32$$