Probability Divisible 35 Ac106A

1. **State the problem:** We want to find the probability that $2^m + 3^n$ is divisible by $35$ when $m$ and $n$ are chosen from $\{1,2,\dots,600\}$ independently and uniformly. 2. **Key idea:** Since $35 = 5 \times 7$, $2^m + 3^n$ divisible by $35$ means divisible by both $5$ and $7$. 3. **Divisibility conditions:** - $2^m + 3^n \equiv 0 \pmod{5}$ - $2^m + 3^n \equiv 0 \pmod{7}$ 4. **Analyze modulo 5:** - The order of $2$ mod $5$ is $4$ because $2^4 = 16 \equiv 1 \pmod{5}$. - The order of $3$ mod $5$ is also $4$ because $3^4 = 81 \equiv 1 \pmod{5}$. So $2^m$ mod $5$ and $3^n$ mod $5$ cycle every $4$ steps. 5. **Possible values mod 5:** - $2^m$ mod $5$ cycles as: $2,4,3,1$ for $m \equiv 1,2,3,0 \pmod{4}$ respectively. - $3^n$ mod $5$ cycles as: $3,4,2,1$ for $n \equiv 1,2,3,0 \pmod{4}$ respectively. 6. **Condition $2^m + 3^n \equiv 0 \pmod{5}$ means:** $$2^m \equiv -3^n \equiv 5 - 3^n \pmod{5}$$ Check all pairs $(m \bmod 4, n \bmod 4)$: - $(1,1): 2 + 3 = 5 \equiv 0$ - $(2,3): 4 + 2 = 6 \equiv 1$ - $(3,2): 3 + 4 = 7 \equiv 2$ - $(0,0): 1 + 1 = 2 \neq 0$ Check all systematically: | $m\bmod4$ | $2^m$ mod 5 | $n\bmod4$ | $3^n$ mod 5 | Sum mod 5 | |---|---|---|---|---| |1|2|1|3|5=0| |1|2|2|4|6=1| |1|2|3|2|4| |1|2|0|1|3| |2|4|1|3|7=2| |2|4|2|4|8=3| |2|4|3|2|6=1| |2|4|0|1|5=0| |3|3|1|3|6=1| |3|3|2|4|7=2| |3|3|3|2|5=0| |3|3|0|1|4| |0|1|1|3|4| |0|1|2|4|5=0| |0|1|3|2|3| |0|1|0|1|2| Pairs with sum $\equiv 0 \pmod{5}$ are: $(1,1), (2,0), (3,3), (0,2)$. 7. **Analyze modulo 7:** - The order of $2$ mod $7$ is $3$ because $2^3=8 \equiv 1 \pmod{7}$. - The order of $3$ mod $7$ is $6$ because $3^6=729 \equiv 1 \pmod{7}$. 8. **Possible values mod 7:** - $2^m$ mod $7$ cycles every $3$: $2,4,1$ for $m \equiv 1,2,0 \pmod{3}$. - $3^n$ mod $7$ cycles every $6$: $3,2,6,4,5,1$ for $n \equiv 1,2,3,4,5,0 \pmod{6}$. 9. **Condition $2^m + 3^n \equiv 0 \pmod{7}$ means:** $$2^m \equiv -3^n \equiv 7 - 3^n \pmod{7}$$ Check all pairs $(m \bmod 3, n \bmod 6)$: - For $m=0$: $2^m=1$ - For $m=1$: $2$ - For $m=2$: $4$ Check $3^n$ values and sums: | $m\bmod3$ | $2^m$ mod 7 | $n\bmod6$ | $3^n$ mod 7 | Sum mod 7 | |---|---|---|---|---| |0|1|0|1|2| |0|1|1|3|4| |0|1|2|2|3| |0|1|3|6|0| |0|1|4|4|5| |0|1|5|5|6| |1|2|0|1|3| |1|2|1|3|5| |1|2|2|2|4| |1|2|3|6|1| |1|2|4|4|6| |1|2|5|5|0| |2|4|0|1|5| |2|4|1|3|0| |2|4|2|2|6| |2|4|3|6|3| |2|4|4|4|1| |2|4|5|5|2| Pairs with sum $\equiv 0 \pmod{7}$ are: $(0,3), (1,5), (2,1)$. 10. **Combine modulo 5 and modulo 7 conditions:** - $m$ must satisfy both mod 4 and mod 3 conditions. - $n$ must satisfy both mod 4 and mod 6 conditions. 11. **Find combined conditions for $m$:** - From mod 5: $m \bmod 4 \in \{0,1,2,3\}$ (specific values from step 6) - From mod 7: $m \bmod 3 \in \{0,1,2\}$ (specific values from step 9) Pairs for $m$ from step 6: $m \bmod 4$ in $\{1,2,3,0\}$ with corresponding $n \bmod 4$. Pairs for $m$ from step 9: $m \bmod 3$ in $\{0,1,2\}$ with corresponding $n \bmod 6$. 12. **List all $(m \bmod 12)$ that satisfy both mod 4 and mod 3 conditions:** - Since $12$ is lcm of $3$ and $4$, use Chinese remainder theorem. From mod 5 condition for $m$: - $m \bmod 4 = 1,2,3,0$ (all possible) From mod 7 condition for $m$: - $m \bmod 3 = 0,1,2$ (all possible) So all $m \bmod 12$ are possible. 13. **Similarly for $n$:** - From mod 5: $n \bmod 4 \in \{1,2,3,0\}$ (specific values) - From mod 7: $n \bmod 6 \in \{0,1,2,3,4,5\}$ (all possible) 14. **Check combined $(n \bmod 12)$ values that satisfy both conditions:** - Use CRT for mod 4 and mod 6 (lcm 12). From mod 5 condition for $n$: - $n \bmod 4$ must be in $\{1,2,3,0\}$ (all possible) From mod 7 condition for $n$: - $n \bmod 6$ must be in $\{3,5,1\}$ (from step 9 pairs) 15. **Find all $n \bmod 12$ satisfying $n \bmod 4$ and $n \bmod 6$ conditions:** - $n \bmod 6$ in $\{3,5,1\}$ - $n \bmod 4$ in $\{1,2,3,0\}$ Check each $n \bmod 6$ with $n \bmod 4$: - $n \equiv 3 \pmod{6}$: possible $n \bmod 4$ are $3$ (since $3 \bmod 4=3$) - $n \equiv 5 \pmod{6}$: $5 \bmod 4=1$ - $n \equiv 1 \pmod{6}$: $1 \bmod 4=1$ So valid $n \bmod 12$ are: - $n \equiv 3 \pmod{12}$ (since $3 \bmod 4=3$, $3 \bmod 6=3$) - $n \equiv 5 \pmod{12}$ (since $5 \bmod 4=1$, $5 \bmod 6=5$) - $n \equiv 1 \pmod{12}$ (since $1 \bmod 4=1$, $1 \bmod 6=1$) 16. **Similarly for $m$ from combined conditions:** - From step 6, $m \bmod 4$ in $\{1,2,3,0\}$ - From step 9, $m \bmod 3$ in $\{0,1,2\}$ All $m \bmod 12$ are possible. 17. **Count valid pairs $(m,n)$ mod $(12,12)$:** - $m$ can be any of $12$ residues. - $n$ can be only $3$ residues: $1,3,5$ mod 12. 18. **Total pairs mod 12:** $12 \times 12 = 144$ Valid pairs: $12 \times 3 = 36$ 19. **Since $m,n$ are chosen from $1$ to $600$, and $600$ is divisible by $12$, the distribution of residues mod 12 is uniform.** 20. **Probability:** $$\frac{36}{144} = \frac{1}{4}$$ **Final answer:** $$\boxed{\frac{1}{4}}$$