Please suggest a suitable approach for this problem.
$\endgroup$ 46 Answers
$\begingroup$Well... $4^{44}$ is obviously divisible by 4, that is, $4^{44} \equiv 0 \pmod 4$. So you only need to calculate $4^{44} \pmod {11}$, which can be done using Fermat's Little Theorem (since 4 and 11 are coprime), then use the Chinese Remainder Theorem to combine the two congruences.
$\endgroup$ 3 $\begingroup$$4^{44}=4^4\times4^{40}=4^4\times(4^{10}-1+1)^4$. The second factor leaves remainder 1 one divided by 11. This is because of Fermat's little theorem, but can be seen directly: $4^{10}-1=(2^{10}-1)(2^{10}+1)=11\times93\times1025$, so $4^{10}$ is a multiple of 11 plus 1, and so is $4^{40}$. Finally, $4^{44}=4^4\times(11k+1)\equiv 4^4=256=44\times5+36\equiv 36\pmod{44}$.
The key is to consider the prime decomposition of 44 and treat each factor separately.
$\endgroup$ $\begingroup$One way to do this is to figure out that
$ 4^6 \equiv 64^2 \equiv 20^2 \equiv 4 \mod 44 $
Thus
$ 4^{44} \equiv (4^6)^7 * 4^2 \equiv 4^7 * 4^2 \equiv 4^4 \equiv 36 \mod 44 $
so the answer is $36$, and all you had to do is calculate a few powers of $4$ mod $44$.
$\endgroup$ $\begingroup$Another method is to simply compute $4^{44} \pmod {44}$, which could be done in any self-respecting computer algebra system (or you could write your own code for it, watching out for overflow errors). For example: you could use WolframAlpha.
Warning: If this is a homework question, finding the answer computationally is likely to annoy the lecturer. However, it's still a good way to check your answer.
$\endgroup$ 2 $\begingroup$As previously stated, since $4^{44} \equiv 0 \pmod 4$, all you need to find is $4^{44} \mod 11$ (which makes sense if you think about the fact that if $4^{44}$ is evenly divisible by one factor of 44, it won't affect the result of modding, so you only need to consider the other factor, 11).
A faster way to do this is note that $4^{44}=2^{88}=2^{85}\cdot8=32^{17}\cdot8$, and that $32\equiv -1 \pmod{11}$, which turns it into $(-8)\mod 11$. However, it is important to note that this is still in mod 11, so the answer must be turned into $(-8)\mod 44$. (which is the same thing, as we noted earlier)
$\endgroup$ 0 $\begingroup$$\rm\ 4^5\equiv 2^{10}\equiv 1\ \:(mod\ 11)\ \Rightarrow\ 4^{4+5\cdot8}\equiv 4^4\equiv 4\cdot 20\equiv -8\ (mod\ 11)\:$ and $\rm (mod\ 4)\:$, so $\rm (mod\ 44)$
$\endgroup$ 1
