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"

(Created page with "==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>...")
 
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
 +
Let <math>a = 2^{w+3}3^x5^{y+1}7^zT</math> and <math>b = 2^w3^{x+2}5^y7^{z+1}T</math>, where <math>w</math>, <math>x</math>, <math>y</math>, and <math>z</math> are all nonnegative integers and <math>T</math> is a positive integer not divisible by any of <math>2</math>, <math>3</math>, <math>5</math>, and <math>7</math>. Then,
 +
<cmath>\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})}.</cmath>Now, we determine the possible values of each factor on the right hand side based on the values of <math>w</math>, <math>x</math>, <math>y</math>, and <math>z</math>.
 +
<UL><LI>If <math>w=0</math>, then <math>\tfrac{\varphi(2^{w+3})}{\varphi(2^{w})} = 4</math>; if <math>w>0</math>, then <math>\tfrac{\varphi(2^{w+3})}{\varphi(2^{w})} = \tfrac{2^{w+2}\varphi(2)}{2^{w-1}\varphi(2)} = 8</math>.</LI>
 +
<LI>If <math>x=0</math>, then <math>\tfrac{\varphi(3^{x})}{\varphi(3^{x+2})} = \tfrac{1}{6}</math>; if <math>x>0</math>, then <math>\tfrac{\varphi(3^{x})}{\varphi(3^{x+2})} = \tfrac{3^{x-1}\varphi(3)}{3^{x+1}\varphi(3)} = \tfrac{1}{9}</math>.</LI>
 +
<LI>If <math>y=0</math>, then <math>\tfrac{\varphi(5^{y+1})}{\varphi(5^{y})} = 4</math>; if <math>y>0</math>, then <math>\tfrac{\varphi(5^{y+1})}{\varphi(5^{y})} = \tfrac{5^{y}\varphi(5)}{5^{y-1}\varphi(5)} = 5</math>.</LI>
 +
<LI>If <math>z=0</math>, then <math>\tfrac{\varphi(7^{z})}{\varphi(7^{z+1})} = \tfrac{1}{6}</math>; if <math>z>0</math>, then <math>\tfrac{\varphi(7^{z})}{\varphi(7^{z+1})} = \tfrac{7^{z-1}\varphi(7)}{7^{z}\varphi(7)} = \tfrac{1}{7}</math>.</LI></UL>
 +
Thus, the sum of all possible values of <math>\tfrac{\varphi(a)}{\varphi(b)}</math> is<cmath>(4+8)(\tfrac{1}{6}+\tfrac{1}{9})(4+5)(\tfrac{1}{6}+\tfrac{1}{7}) = \frac{65}{7}.</cmath>We extract <math>65+7 = \boxed{72}</math>.

Revision as of 21:50, 9 September 2025

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}$.

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