Problem 548

Suppose that $(205800, 35k)$ is a happy pair. We find the prime factorization of 205800: $205800 = 2^3 \times 3^1 \times 5^2 \times 7^3$. Note also that $35k = 5^1 \times 7^1 \times k$. Let $d$ be the greatest common divisor of 205800 and $35k$. We want to find the number of possible values of $k \leq 2940$ for which $d$ is a perfect square. Since both 5 and 7 are prime divisors of 205800 and $35k$, then 5 and 7 are both prime divisors of $d$. For $d$ to be a perfect square, 5 and 7 must both divide $d$ an even number of times. Since the prime powers of 5 and 7 in the prime factorization of 205800 are $5^2$ and $7^3$, respectively, then for $d$ to be a perfect square, it must be the case that $5^2$ and $7^2$ are factors of $d$. Since $d = 5 \times 7 \times k$, then $k = 5 \times 7 \times j = 35j$ for some positive integer $j$. Since $k \leq 2940$, then $35j \leq 2940$ which gives $j \leq 84$. We now know that $d$ is the gcd of $2^3 \times 3^1 \times 5^2 \times 7^3$ and $5^2 \times 7^2 \times j$. What further information does this give us about $j$? - $j$ cannot be divisible by 3, otherwise $d$ would have a factor of $3^1$ and cannot have a factor of $3^2$ which would mean that $d$ is not a perfect square. - $j$ cannot be divisible by 7, otherwise $d$ has a factor of $7^3$ and no larger power of 7, in which case $d$ would not be a perfect square. - If $j$ is divisible by 2, then the prime factorization of $j$ must include $2^2$. In other words, the prime factorization of $j$ cannot include $2^1$ or $2^3$. - $j$ can be divisible by 5 since even if $j$ is divisible by 5, the power of 5 in $d$ is already limited by the power of 5 in 205800. - $j$ can be divisible by prime numbers other than $2, 3, 5$ or 7 since 205800 is not and so the gcd will not be affected. Finally, we consider two cases: $j$ is divisible by $2^2$ but not by a larger power of 2, and $j$ is not divisible by 2. Case 1: $j$ is divisible by $2^2$ but not by a larger power of 2 Here, $j = 2^2h = 4h$ for some odd positive integer $h$. Since $j \leq 84$, then $4h \leq 84$ which means that $h \leq 21$. Knowing that $j$ cannot be divisible by 3 or by 7, this means that the possible values of $h$ are $1, 5, 11, 13, 17, 19$. Each of these values of $h$ produces a value of $j$ that satisfies the conditions in the five bullets above. There are thus 6 values of $j$ in this case. Case 2: $j$ is not divisible by 2 Here, $j$ is odd. Knowing that $j$ cannot be divisible by 3 or by 7 and that $j \leq 84$, this means that the possible values of $j$ are: $1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 79, 83$. There are thus 24 values of $j$ in this case. In total, there are 30 values of $j$ and so there are 30 possible values of $k \leq 2940$ for which $(205800, 35k)$ is a happy pair.