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.

Find the smallest number $m$ such that $4^{32}+25^{433}+m$ is divisible by $7$.

We went over this in class a while ago, but I can't figure out how to do problems like this.

share|improve this question
2  
You already asked a very similar question just yesterday: what did you learn from the numerous answers/comments you got there? At least give us some ideas and show some self effort here. –  DonAntonio Nov 28 '12 at 14:13
    
That was for 9s, so it didn't particularly help in a wide variety of cases. I'm looking for a more general rule of how to solve, rather than just an answer. –  Doug Smith Nov 28 '12 at 14:15
    
What "9's"? There appeared 9, 19, 4...it was pretty general! –  DonAntonio Nov 28 '12 at 14:18
    
@DougSmith I suggest you should accept an answer that you found most useful in your previous question, which was very similar to this one. And after a while, accept an answer for this question too, if your question is answered. –  Paresh Nov 28 '12 at 15:50

3 Answers 3

up vote 2 down vote accepted

Applying Fermat's Little Theorem, $4^{7-1}\equiv 1\pmod 7\implies (4^6)^5\equiv 1$

So, $4^{32}=4^2\cdot 4^{30}\equiv 4^2\pmod 7\equiv 2$

Similarly, $25^6\equiv1\pmod 7$ and $433\equiv1\pmod 6\implies 25^{433}\equiv 25\pmod 7\equiv 4$

So, $4^{32}+25^{433}\equiv2+4\pmod 7\equiv 6$

So, the smallest positive integer value of $m$ is $7-(6)=1$

share|improve this answer

Basically what you're asking is: for what (smallest positive integer) $m$ holds $4^{32} + 25^{433} + m \pmod{7} = 0$

So what you would want to do is calculate $4^{32} \pmod{7}$ and $25^{433} \pmod{7}$ and add these together in mod 7 and then see what the remainder is.

$1 * 4^{32} \pmod{7} = 1 * 2^{16} =$ (because $4^2 \pmod{7} = 2$, halving the exponent) $1 * 4^8 = 1 * 2^4 = 1 * 4^2 = 1 * 2^1 = 2$

$4^{32} \pmod{7} = 2$

$1 * 25^{433} \pmod{7} = 4 * 2^{216} = 4 * 4^{108} = 4 * 2^{54} = 4 * 4^{27} = 2 * 2^{13} = 4 * 4^6 = 4 * 2^3 = 1 * 4^1 = 4$

So, $4^{32} = 2$ and $25^{433} = 4$, $4 + 2 = 6$, What is the remainder to get 0 in mod 7?

If you don't know this method, it's called exponentiation by squaring, I did it rather quick and I'm not sure whether you were able to follow it. The = symbols should be interpreted as triple bar symbols. http://en.wikipedia.org/wiki/Exponentiation_by_squaring

share|improve this answer

Hint $\rm\,\ mod\ 7\!:\,\ 0 \equiv 4^\color{#C00}3\!-\!1\equiv (4\!-\!1)(4^2\!+4+1)\:\Rightarrow\:4^2\!+4+1\equiv 0\:\Rightarrow\:4^{2+\color{#C00}3J}\!\!+4^{1+\color{#C00}3K}\!\!+1\equiv 0$

share|improve this answer

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.