Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please suggest a suitable approach for this problem.

share|improve this question
    
Also, moderators, what is the policy on [tastes-like-homework] questions? –  Mark C Nov 1 '10 at 4:20
1  
    
@Kenny Thanks for the link. –  Mark C Nov 1 '10 at 15:31
add comment

6 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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
2  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this 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
1  
PowerMod[4,44,44]. –  J. M. Oct 31 '10 at 4:00
add comment

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)

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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