# What is the remainder when $4^{44}$ is divided by 44?

Please suggest a suitable approach for this problem.

-
Also, moderators, what is the policy on [tastes-like-homework] questions? –  Mark C Nov 1 '10 at 4:20
–  KennyTM Nov 1 '10 at 6:36
@Kenny Thanks for the link. –  Mark C Nov 1 '10 at 15:31

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.

-
Will you please explain how you conclude from $4^{44} \equiv 0 \pmod 4$ that we need to calculate $4^{44} \pmod {11}$ ? –  Quixotic Oct 31 '10 at 2:22
The Chinese Remainder Theorem is capable of telling us the value of x (mod n) from knowledge of x (mod a) and x (mod b) whenever gcd(a,b)=1 and ab=n. In this case, we have n=44, and know the congruence (mod 4), which leaves (mod 11). –  Douglas S. Stones Oct 31 '10 at 2:37
@Tretwick I think Doulgas answered your question, but in an oblique way. You want to check for divisibility by 44 = 4 * 11. Four raised to any power is divisible by four, so the remaining condition is that it is also divisible by eleven. –  Mark C Nov 1 '10 at 4:13

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

-

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

-

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.

-
Hmm this comes from my test paper so I don't like to use, however I will be happy to know how to do the same in Mathematica 7.0 >! –  Quixotic Oct 31 '10 at 2:26
PowerMod[4,44,44]. –  Ｊ. Ｍ. Oct 31 '10 at 4:00

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)

-

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

-
Douglas: No, the RHS congruence is true mod 11 (by LHS) and it is trivially true mod 4 (all being 0), so it's true mod lcm(4,11) = 44; i.e if 4,11|A-B then 44|A-B. I edited the answer to make this clearer. –  Bill Dubuque Oct 31 '10 at 16:23