*Posted by Alex in : potd , trackback
*
Find the number of ordered pairs of positive integers $(a, b)$ such that $$\gcd(ax^2 + 36, 2x + b)\equiv\frac{72 – abx}{2}\pmod{2x+b}$$ as long as $x$ is a positive integer.

show

**Solution:**
The Euclidean algorithm is useful here. It states that $$ \gcd(a, b)= \begin{cases} a, & \text{if }b=0 \\ \gcd(b, a\bmod{b}), & \text{otherwise} \end{cases} $$ Thus, we can use this algorithm repeatedly to modify the left side of the equation. $$ \gcd(ax^2 + 36, 2x + b)\equiv\frac{72 – abx}{2}\pmod{2x+b}$$ $$\gcd(2x+b, 36-\frac{ab}{2}x)\equiv\frac{72 – abx}{2}\pmod{2x+b}$$ $$\gcd(36-\frac{ab}{2}x, b-\frac{144}{ab})\equiv\frac{72 – abx}{2}\pmod{2x+b} $$ Because $36-\frac{ab}{2}x=\frac{72-abx}{2}$ is the greatest common divisor we are looking for, $b-\frac{144}{ab}$ must equal $0$. This occurs when $$ab^2=144$$ In order to find the number of solutions, we note that because $144$ is a perfect square and $b^2$ is also a perfect square, $a$ must be a perfect square. Since $144=2^4\cdot3^2$, $a$ is in the form of $2^{2n}\cdot3^{2m}$, where $n$ can be $0$, $1$, or $2$, and $m$ can be $0$ or $1$. By multiplying the number of possibilities for $n$ and the number of possibilities for $m$ together, we see that the answer is $3\cdot2=\boxed{6}$.

## Comments»

no comments yet - be the first?