2025 SSMO Speed Round Problems/Problem 7

Problem

Positive integers $a$ and $b$ satisfy $63a = 40b$ . The sum of all possible values of $\tfrac{\varphi(a)}{\varphi(b)}$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution

Let $a = 2^{w+3}3^x5^{y+1}7^zT$ and $b = 2^w3^{x+2}5^y7^{z+1}T$ , where $w$ , $x$ , $y$ , and $z$ are all nonnegative integers and $T$ is a positive integer not divisible by any of $2$ , $3$ , $5$ , and $7$ . Then, $\frac{\varphi(a)}{\varphi(b)} = \frac{\varphi(2^{w+3})}{\varphi(2^{w})} \cdot \frac{\varphi(3^{x})}{\varphi(3^{x+2})} \cdot \frac{\varphi(5^{y+1})}{\varphi(5^{y})} \cdot \frac{\varphi(7^{z})}{\varphi(7^{z+1})}.$ Now, we determine the possible values of each factor on the right hand side based on the values of $w$ , $x$ , $y$ , and $z$ .

If $w=0$ , then $\tfrac{\varphi(2^{w+3})}{\varphi(2^{w})} = 4$ ; if $w>0$ , then $\tfrac{\varphi(2^{w+3})}{\varphi(2^{w})} = \tfrac{2^{w+2}\varphi(2)}{2^{w-1}\varphi(2)} = 8$ .
If $x=0$ , then $\tfrac{\varphi(3^{x})}{\varphi(3^{x+2})} = \tfrac{1}{6}$ ; if $x>0$ , then $\tfrac{\varphi(3^{x})}{\varphi(3^{x+2})} = \tfrac{3^{x-1}\varphi(3)}{3^{x+1}\varphi(3)} = \tfrac{1}{9}$ .
If $y=0$ , then $\tfrac{\varphi(5^{y+1})}{\varphi(5^{y})} = 4$ ; if $y>0$ , then $\tfrac{\varphi(5^{y+1})}{\varphi(5^{y})} = \tfrac{5^{y}\varphi(5)}{5^{y-1}\varphi(5)} = 5$ .
If $z=0$ , then $\tfrac{\varphi(7^{z})}{\varphi(7^{z+1})} = \tfrac{1}{6}$ ; if $z>0$ , then $\tfrac{\varphi(7^{z})}{\varphi(7^{z+1})} = \tfrac{7^{z-1}\varphi(7)}{7^{z}\varphi(7)} = \tfrac{1}{7}$ .

Thus, the sum of all possible values of $\tfrac{\varphi(a)}{\varphi(b)}$ is $(4+8)(\tfrac{1}{6}+\tfrac{1}{9})(4+5)(\tfrac{1}{6}+\tfrac{1}{7}) = \frac{65}{7}.$ We extract $65+7 = \boxed{72}$ .

Page

Toolbox

Search

2025 SSMO Speed Round Problems/Problem 7

Problem

Solution