Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2025 SSMO Speed Round Problems/Problem 7"

m (→‎Solution)
m (→‎Problem)
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
Positive integers <math>a</math> and <math>b</math> satisfy <math>63a = 40b</math>. The sum of all possible values of <math>\tfrac{\varphi(a)}{\varphi(b)}</math> is <math>\frac{m}{n},</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
+
Positive integers <math>a</math> and <math>b</math> satisfy <math>63a = 40b</math>. The sum of all possible values of <math>\tfrac{\varphi(a)}{\varphi(b)}</math> is <math>\tfrac{m}{n},</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
  
 
==Solution==
 
==Solution==

Latest revision as of 15:13, 10 September 2025

Problem

Positive integers $a$ and $b$ satisfy $63a = 40b$. The sum of all possible values of $\tfrac{\varphi(a)}{\varphi(b)}$ is $\tfrac{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}) = \tfrac{65}{7}.\]We extract $65+7 = \boxed{72}$.

~Sedro

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_SSMO_Speed_Round_Problems/Problem_7&oldid=260312"