Permutations & Combinations
Modular Arithmetic Pairs — p+q
nta_pyq_2026_jan
Grade 11
Question:
Let $S=\{(m,n):m,n\in\{1,2,3,\ldots,50\}\}$. If the number of elements $(m,n)$ in $S$ such that $6^m+9^n$ is a multiple of 5 is $p$ and the number of elements $(m,n)$ in $S$ such that $m+n$ is a square of a prime number is $q$, then $p+q$ is equal to _____.
Step-by-Step Solution
Key Concept: $6\equiv1$, $9\equiv-1\pmod5$. $6^m+9^n\equiv1+(-1)^n\pmod5=0$ only when $n$ is odd. Odd $n$ in $\{1,\ldots,50\}$: 25. $p=50\times25=1250$. For $m+n=$ square of prime: $4,9,25,49$ (primes 2,3,5,7). Pairs: $m+n=4$: 3, $m+n=9$: 8, $m+n=25$: 24, $m+n=49$: 48.
$p=1250$, $q=83$. $p+q=1333$.
Correct Answer: 1333