0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "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$. $\endgroup$ – fleablood Mar 14 '18 at 0:43
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.