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