Question

If 5 divides ${{6}^{n}}+{{9}^{m}}$, where $m,n\in \left\{ 1,2,3,\cdots ,50 \right\}$, then the number of possible ordered pairs (m,n) is
[a] 1250
[b] 2500
[c] 625
[d] 500

Answer 1

Hint: Use the fact that $6=5+1$ and $9=10-1$ and hence prove that ${{6}^{n}}+{{9}^{m}}={{\left( 5+1 \right)}^{n}}+{{\left( 10-1 \right)}^{m}}$
Use the fact that ${{\left( a+b \right)}^{n}}{{=}^{n}}{{C}_{0}}{{a}^{n}}{{+}^{n}}{{C}_{1}}{{a}^{n-1}}b+\cdots {{+}^{n}}{{C}_{n-1}}a{{b}^{n-1}}{{+}^{n}}{{C}_{n}}{{b}^{n}}$. Hence prove that ${{6}^{n}}+{{9}^{m}}$ is divisible by 5 if and only if ${{\left( 1 \right)}^{n}}+{{\left( -1 \right)}^{m}}$ is divisible by 5. Use the fact that whenever m is odd ${{1}^{n}}+{{\left( -1 \right)}^{m}}$ is divisible by 5. Hence prove that the number of ordered pairs (m,n) is equal to the number of ways in which we can select m and n such that m is odd. Hence determine which of the options is correct.
Complete step-by-step solution:
We know that $6=5+1$ and $9=10-1$
Hence, we have
${{6}^{n}}+{{9}^{m}}={{\left( 5+1 \right)}^{n}}+{{\left( 10-1 \right)}^{m}}$
We know that ${{\left( a+b \right)}^{n}}{{=}^{n}}{{C}_{0}}{{a}^{n}}{{+}^{n}}{{C}_{1}}{{a}^{n-1}}b+\cdots {{+}^{n}}{{C}_{n-1}}a{{b}^{n-1}}{{+}^{n}}{{C}_{n}}{{b}^{n}}$.(This is known as binomial theorem).
Hence, we have
$\begin{align}
  & {{6}^{n}}+{{9}^{m}}{{=}^{n}}{{C}_{0}}{{+}^{n}}{{C}_{1}}5{{+}^{n}}{{C}_{2}}{{5}^{2}}+\cdots {{+}^{n}}{{C}_{n-1}}{{5}^{n-1}}{{+}^{n}}{{C}_{n}}{{5}^{n}}{{+}^{m}}{{C}_{0}}{{\left( -1 \right)}^{m}}{{+}^{m}}{{C}_{1}}{{\left( -1 \right)}^{m-1}}10+\cdots \\
 & {{+}^{m}}{{C}_{m-1}}\left( -1 \right){{10}^{m-1}}{{+}^{,m}}{{C}_{m}}{{10}^{m}} \\
\end{align}$
All the terms containing powers of 5 and 10 are divisible 5.
Hence the remainder obtained on dividing ${{6}^{n}}+{{9}^{m}}$ by 5 is equal to $^{n}{{C}_{0}}{{+}^{m}}{{C}_{0}}{{\left( -1 \right)}^{m}}$
We know that $^{n}{{C}_{0}}=1$. Hence, we have
$^{n}{{C}_{0}}{{+}^{m}}{{C}_{0}}{{\left( -1 \right)}^{m}}=1+{{\left( -1 \right)}^{m}}$
The set $\left\{ 1+{{\left( -1 \right)}^{m}},m\in \mathbb{Z} \right\}$ is equal to $\left\{ 2,0 \right\}$ since there are only two possible 2( when m is even) and 0 (when m is odd).
Of these two numbers, only 0 is divisible by 5.
Hence, we have
${{6}^{n}}+{{9}^{m}}$ is divisible by 5 if and only if $1+{{\left( -1 \right)}^{m}}=0$ i.e. m is odd.
Hence the number of pairs (m,n) such that ${{6}^{n}}+{{9}^{m}}$ is divisible by 5 is equal to the number of ways in which we can select m and n such that m is odd.
Here $m,n\in \left\{ 1,2,3,\cdots ,50 \right\}$
Of these 50 numbers 25 are odd.
Hence the number of ways in which m can be selected is 25 and the number of ways in which n can be selected is 50
Hence the number of ordered pairs (m,n) is $50\times 25=1250$
Hence option [a] is correct.

Note: Alternative Solution: Using Congruences
We know that if $a\equiv b\left( \big | m \right)$, then $m$ divides $a-b$
Since 5 divides 6-1, we have $6\equiv 1\left( \big | 5 \right)$
Since 5 divides $9-\left( -1 \right)$, we have $9\equiv -1\left( \big | m \right)$
We know that if $a\equiv b\left( \big | m \right)$, then ${{a}^{x}}\equiv {{b}^{x}}\big | \left( m \right)$
Hence, we have
${{6}^{n}}\equiv {{\left( 1 \right)}^{n}}\left( \big | 5 \right)$ and ${{9}^{m}}\equiv {{\left( -1 \right)}^{m}}\big | 5$
We know that if $a\equiv b\left( \big | m \right)$ and $c\equiv d\left( \big | m \right)$, then $a+c\equiv \left( b+d \right)\left( \big | m \right)$
Hence, we have
${{6}^{n}}+{{9}^{m}}\equiv 1+{{\left( -1 \right)}^{m}}\left( \big | 5 \right)$
We know that if $m$ divides a, then $a\equiv 0\left( \big | m \right)$
Hence, we have
5 divides${{6}^{n}}+{{9}^{n}}$ if and only $1+{{\left( -1 \right)}^{m}}\left( \big | 5 \right)$
Since $1+{{\left( -1 \right)}^{m}}\in \left\{ 0,2 \right\}$ and of these only $0\equiv 0\left( \big | 5 \right)$
Hence, we have
$1+{{\left( -1 \right)}^{m}}=0\Rightarrow m\text{ is odd}$, which is the same as obtained above
Hence proceeding similarly as above, we get [a] as the correct answer.