$ 7^{50} \cdot 4^{102} ≡ x \pmod {110} $

Question

The way I would solve this would be: $$ (7^3)^{15} \cdot 7^5 \cdot (4^4)^{25} \cdot 4^2 $$ and take it from there, but I know that this is most likely in an inefficient way. Does anyone have more efficient methods?

Answer 1

Do prime factorization on $110$. It's $110 = 5 \cdot 2 \cdot 11$.

Now work with the prime factors as moduli.

$$7^{50} \cdot 4^{102} \equiv 0 \pmod 2 \text{ trivial, as 2 \mid 4}$$

Then apply Fermat's Little Theorem so we have:

$$7^4 \equiv 1 \pmod 5 \implies 7^{50} \equiv 49 \equiv 4 \pmod 5$$ $$4^4 \equiv 1 \pmod 5 \implies 4^{102} \equiv 4^2 \equiv 1 \pmod 5$$

Now multiply them and we have:

$$7^{50} \cdot 4^{102} \equiv 4 \cdot 1 \equiv 4 \pmod 5$$

Now repeat the method with the last factor:

$$7^{10} \equiv 1 \pmod {11} \implies 7^{50} \equiv 1 \pmod {11}$$ $$4^{10} \equiv 1 \pmod {11} \implies 4^{102} \equiv 4^2 \equiv 16 \equiv 5 \pmod {11}$$

Multiply them and we have:

$$7^{50} \cdot 4^{102} \equiv 1 \cdot 5 \equiv 5 \pmod {11}$$

Now just apply CRT to the three congruence relation to get the final answer.

Answer 2

$4^{102}$ is just $2^{204}$ therefore $7^{50}*4^{102}\equiv 7^{50}*2^{204}\bmod 110$. So if we can find a reduced number to which $2^{204}$ is congruent to mod 55 then we can know its congruence mod 110 since we know its even.

using euler's theorem we get that $2^{\phi (55)}\equiv 1 \bmod55$

since $\phi(55)=40$

$2^{204}\equiv 2^4 \bmod 55$ so $2^{204}\equiv 16 \bmod110$.

using the fact that $\phi(110)$ is $40$

we get $7^{50} \equiv 7^{10}$ make a list:

7,49,13,91,87,59,83,31,107,89.

Therefore :$7^{50}*4^{102}\equiv 89*16\equiv 104 \bmod 110$

Answer 3

Hint: Do them separately by means of successive squaring. To start off we would do,

We need to get to $7^{50} = (7^5)^{10}$

$7\equiv 7 (mod\ 110)$, $7^2\equiv 7x7=49 (mod\ 110)$ $(7^2)^2 = 7^4 \equiv (49)^2=2401\equiv 91 (mod\ 110)$, $(7^4)^2 = 7^8\equiv 91*91 =8281\equiv 31 (mod 110),(7^8)^2 = 7^{16}\equiv 31*31 = 961\equiv 81 (mod110), (7^{16})^2=7^{32}\equiv 81*81 = 6561\equiv 71 (mod 110)$.

Well, $7^{50} = 7^{32}*7^{16}*7^2\equiv 71*81*49 \equiv 89 (mod 110)$.

Now use the same method for $4^{102}$ and multiply.

$(4^2)^2 = 4^4 = 256\equiv 36 (mod 110), (4^4)^2 = 4^8\equiv 36^2 = 86 (mod 110),(4^8)^2 = 4^16 = 86^2=7396\equiv 26 (mod 110), (4^{16})^2 = 4^{32}\equiv 26^2 = 676\equiv 16 (mod110), (4^{32})^2 = 4^{64}\equiv 16*16 = 256\equiv 36 (mod110)$.

Well, $4^{102} = 4^{64}*4^{32}*4^{4}*4^2\equiv 36*16*36*16 = 36^2*16^2\equiv 86*36 = 3096\equiv 16 mod 110.$

Hence, $7^{50}*4^{102}\equiv 16*89=1424\equiv 104 (mod 110)$.

Okay this isn't efficient, I just had to finish.