Let m and n,(m

Question

Let m and $n,(m<n)$, be two 2-digit numbers. Then the total numbers of pairs $(m,n)$, such that $gcd(m,n)=6$, is \_\_\_\_\_\_\_\_\_\_ .

Answer: 64

Accepted Answer

$\begin{gathered} m=6a,n=6b \ gcd(m,n)=6\Rightarrow gcd(a,b)=1 \ m=6a\ge 10\Rightarrow a\ge [\frac{10}{6}]=2 \ m=6a\le 99\Rightarrow a\le [\frac{99}{6}]=16 \end{gathered}$

So $a,b\in {2,3,\ldots ,16}$, and we count how many coprime pairs $(a,b)$ with $a$$$\begin{gathered} a=2\Rightarrow b=3,5,7,9,11,13,15\Rightarrow 7 \ a=3\Rightarrow b=4,5,7,8,10,11,13,14,16\Rightarrow 9 \ a=4\Rightarrow b=5,7,9,11,13,15\Rightarrow 6 \ a=5\Rightarrow b=6,7,8,9,11,12,13,14,16\Rightarrow 9 \ a=6\Rightarrow b=7,11,13\Rightarrow 3 \ a=7\Rightarrow b=8,9,10,11,12,13,15,16\Rightarrow 8 \ a=8\Rightarrow b=9,11,13,15\Rightarrow 4 \ a=9\Rightarrow b=10,11,13,14,16\Rightarrow 5 \ a=10\Rightarrow b=11,13\Rightarrow 2 \ a=11\Rightarrow b=12,13,14,15,16\Rightarrow 5 \ a=12\Rightarrow b=13,17\times \to 13\Rightarrow 1 \ a=13\Rightarrow b=14,15,16\Rightarrow 3 \ a=14\Rightarrow b=15,\Rightarrow 1 \ a=15\Rightarrow b=16\Rightarrow 1 \end{gathered}$$$

$$$\begin{gathered} =7+9+6+9+3+8+4+5+2+5+1 \ +3+1+1=64 \end{gathered}$$

Solutions · 1