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

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.

• "without using plugging it in somewhere." What's wrong with plugging it in? $40^2 \equiv 1600 \equiv 1600- 3*490\equiv 1600 - 1500 + 30 \equiv 130\equiv 130 - 2*49 \equiv 32$. Or better you $40^2 \equiv (-9)^2 \equiv 81 \equiv 32 \mod 49$. – fleablood Mar 14 '18 at 0:43

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

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

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

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$$