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

Question

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 !!

Answer 1

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

Answer 2

$7\equiv 2 \bmod 5, 2^1 \equiv 2,2^2 \equiv 4, 2^3\equiv 3 ,2^4\equiv 1$. morever if $m\equiv a\bmod4$ then $2^m\equiv2^a$. (because $2^4\equiv 1 \bmod5)$

so if you want the sum to be divisible by 5 there are 4 ways for this to happen:

$m\equiv1$ and $n\equiv4 \bmod 4$

$m\equiv4$ and $n\equiv1 \bmod 4$

$m\equiv2$ and $n\equiv3 \bmod 4$

$m\equiv3$ and $n\equiv2 \bmod 4$

So if m is any congruence class then the probability n is the corresponding correct class is $\frac{1}{4}$

Answer 3

You made three mistakes, or possibly four. One or two of them reside in your calculation $97+93+89+\cdots+2=1224$. It should be $97+93+89+\cdots+1=1225$. It's a little odd that the correction seemingly subtracts $1$ on one side and adds it to the other, so let me spell out the correct calculation:

$$\begin{align} 97+93+89+\cdots+1&=(4\cdot24+1)+(4\cdot23+1)+(4\cdot22+1)+\cdots+(4\cdot1+1)+1\\ &=4(24+23+22+\cdots+1)+25\\ &=4\left({24\cdot25\over2}\right)+25=1225 \end{align}$$

However, these aren't the correct numbers to be adding anyway. The correct calculation would have been

$$98+94+90+\cdots+2=1250$$

This is because the correct sets of values for $n$, corresponding to $m-n=2,6,\ldots,98$ are $(1,2,\ldots,98),(1,2,\ldots,94),\ldots,(1,2)$, since presumably you are allowing $m$ to take the value $100$ as well as $99$.

The final, most substantial error resides in what you did with this number after you got it, which was to divide it by ${100\choose2}=4950$. This computes the probability that of two different numbers the given form will be divisible by $5$. But the problem allows for the two numbers to be the same.

At this point you might be tempted to add the $100$ ways two numbers can be the same to the $4950$ ways they can be different and get $1225/5050=49/202$, but this would also be the wrong answer. The correct thing is to double the number $1225$ to get the total number of ways to choose $m$ and $n$ so that $7^m+7^n$ is divisible by $5$ regardless of which one is larger, and then divide by the total number of ways to choose two numbers between $1$ and $100$, which is simply $100^2=10000$. So the correct answer is $2500/10000=1/4$, as others have pointed out.

All that said, it's worthwhile understanding what you did wrong, and it's also worthwhile understanding (from the answers other people have given) how the problem could have been solved by taking a simpler approach.

Answer 4

Shouldn't the answer be $24/100$? This is because there are 40 numbers which satisfy $7^x = 2^x = 1 \mod 5$, and $20$ each for $7^x = 2^x = 2,3,4 \mod 5$, so we can't just assign equal probabilities to each event. ( Saying equal likeliness of the events $1+4,2+3,3+2,4+1$ as the sum of the remainders out of $4\cdot 4=16$ possible combinations).

The answer should be $$ \frac{40}{100} \cdot \frac{20}{100} + \frac{20}{100} \cdot \frac{20}{100} + \frac{20}{100} \cdot \frac{20}{100} + \frac{20}{100} \cdot \frac{40}{100} = \frac{24}{100}. $$

Answer 5

$7^m+7^n=7^n[7^{m-n}+1]=5k\implies7^{m-n}+1=5q$ since $7^n\notin 5k$

multiples of $7$ ends in the following digits repeats in order $7,9,3,1$. So the only candidates are those ends in $9$. ie,.

$$ m-n=4t+2\\ m-n\in[0,100)\implies 0\leq4t+2<100\implies t\in[0,24.5) $$ Number of favourable cases, ie,. number of possible values of $t$=25

Total number of cases = 100

The Required Probability =$\dfrac{25}{100}=\dfrac{1}{4}$

Answer 6

You did very well until you went off the rails. Notice that $m-n$ can have $1/4$ of possible values. So, for each $n$ you get one quarter of the values of $m$ that work for your condition. So, $1/4$ is the answer.