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

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.

-
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

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$

-

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

-

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$

-