Please suggest a suitable approach for this problem.
What is the remainder when $4^{44}$ is divided by 44?
-
2Also, moderators, what is the policy on **[tastes-like-homework]** questions? – 2010-11-01
-
2@Mark: http://meta.math.stackexchange.com/questions/106/what-is-the-proper-way-to-handle-homework-questions – 2010-11-01
-
0@Kenny Thanks for the link. – 2010-11-01
-
1See also: http://math.stackexchange.com/questions/81228/how-do-i-compute-ab-bmod-c-by-hand – 2016-08-25
6 Answers
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.
-
0Will you please explain how you conclude from $4^{44} \equiv 0 \pmod 4$ that we need to calculate $4^{44} \pmod {11}$ ? – 2010-10-31
-
2The 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). – 2010-10-31
-
0@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. – 2010-11-01
$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.
-
0Hmm 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 >! – 2010-10-31
-
1`PowerMod[4,44,44]`. – 2010-10-31
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)$
-
0Douglas: 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. – 2010-10-31