If the integers m and n are chosen at random between 1 and 100, then the probability that a number of the form $7^{m}+7^{n}$ is divisible by 5 is
$A. 1/4$
$B. 1/7$
$C. 1/8$
$D. 1/49$
I did this: Let $m>n$ (Clearly m and n can't be equal because $5$ can't divide $2*7^{m}$).
Now $7^{m}+7^{n}=7^{n}(7^{m-n}+1)$. If $5$ has to divide this, it implies that 5 has to divide $(7^{m-n}+1)$ (because it cannot divide a power of $7$). Since powers of $7$ have a cyclic order of $7,9,3,1$; $7^{m-n}$ has to therefore end in a $9$ and therefore $m-n$ can be $2,6,10,…,98$. Hence the only set of values of $n$ are $(1,2,3,…,97),(1,2,3,…,93),(1,2,3,…,89),…,(1)$. Also fixing $n$ would fix $m$.
Therefore the number of favorable cases is $97+93+89+…+2=1224$. Which means that the required probability should be $1224/100C2$ which turns out to be $68/275$, which is not matching with any of the options.. Where did I go wrong ??
Please help !!
Best Answer
The numbers are probably intended to be independently chosen, with the possibility that $m=n$. The remainder of $7^m$ on division by $5$ is equally likely to be one of $2,4,3,1$, since $\varphi(5)$ divides $100$. So is the remainder of $7^n$.
Whatever the remainder of $7^m$ happens to be, there is a unique value of $7^n$ modulo $5$ that gives us sum $0$ modulo $5$. That value has probability $\frac{1}{4}$.
Remark: If we choose a pair of numbers (no replacement), then the answer changes. We can assume that the numbers are chosen in order, $m$ first. Whatever value of $m$ is chosen, there are $25$ choices for $n$ that will give sum $0$ modulo $7$, so the probability is $\frac{25}{99}$.