For any positive integer $n$, let $a_n$ be the number of pairs $(x,y)$ of integers satisfying $|x^2-y^2| = n$. (a) Find $a_{1432}$ and $a_{1433}$. (b) Find $a_n$ .
Problem
Source: 2011 Saudi Arabia BMO TST 1.2 - Balkan MO
Tags: number theory
FIREDRAGONMATH16
01.01.2022 04:22
Note that $x^2-y^2 = (x+y)(x-y)$.
We must have either $x^2-y^2=1432$ or $y^2-x^2 = 1432$. Notice that if we select factors $a,b$ of $1432$ such that $ab=1432$, we have the system of equations
$$x+y=a, x-y=b$$or $$x+y=b, x-y=a$$for the first case $x^2-y^2=1432$. Either way, this implies that $x=\frac{a+b}{2}$, which means that $a+b$ is even. Hence for each selection of $(a,b)$, where $a+b$ is even, it contributes $2$ solutions to our total.
Regardless of what odd factors are present, we must decide the distributions of even factors that goes into each of $x+y,x-y$ respectively. Let $m$ and $n$ be the number of factors of two that are present in each of these expressions, respectively. Since $1432= 2^3 \cdot 179$, we obtain $m+n=3$ and seeing our valid distributions as $(1,2), (2,1)$ for our first case. There are $(2 \cdot 2 ) \cdot 2 = 8$ solutions total because we can attack the cases where $y^2-x^2 = 1432$ in a similar fashion. So, $\boxed{a_{1432} = 8}$.
Note that $1433$ is prime. That means that there are two subcases for $x^2-y^2=1433$: either $x+y=1433$ or $x+y=1$ and $x-y$ is purely determined by that selection. There are $2$ cases for this case and $2$ solutions for $y^2-x^2=1433$. Hence, $\boxed{a_{1433} = 2+2 = 4}$.
Remarks. This part (a) is a really good stepping stone for helping us tackle the generalized $a_n$. I'm not sure if it was included in the actual olympiad, but it was a good clue to cue as into focusing in powers of $2$!
parmenides51
02.01.2022 02:41
same idea here