Let A be the set A = {1; 2; 3; … ; 20} containing natural numbers from 1 to 20.
How many ways are there to choose 2 numbers for A such that their product is a multiple of 3?
I tried to take the set B = {3; 6; 9; 12; 15; 18} and taking the combination C(6,1), and C(20, 1). Then I took their product, but I did not succeed.
Can anyone help me overcome this problem?
Thanks in advance.
Best Answer
It is easier to compute the number of ways to choos two numbers such that their product is not a multiple of $3$: since $3$ is prime, it is sufficient to pick two numbers not divisible by $3$.
I make two cases: the two numbers are distinct, or they are equal.
First case: the two numbers are distinct. The non-multiples of $3$ are $14$, so you have $\binom{14}{2}$ pairs of distinct numbers non-multiple of $3$. So, you have $\binom{20}{2} - \binom{14}{2} = 190-91 = 99$ ways to pick two distinct numbers whose product is a multiple of $3$.
Second case: the two numbers are equal. This gives us $6$ ways (picking twice the same multiple of $3$).
Hence, in total, you have $99+6=105$ ways.