Maths Olympiad Prep

Library / /88 of 120

Number theory Difficulty 5.8 AIME, harder Prove it Saudi Arabia

For any positive integer nn let ana_{n} be the number of pairs (x,y)(x, y) of integers satisfying x2y2=n|x^{2}-y^{2}|=n.

a. Find a1432a_{1432} and a1433a_{1433}.

b. Find ana_{n}.

Solution

Let us consider the following cases.

Case 1: nn is odd. The equation x2y2=n|x^{2}-y^{2}|=n is equivalent to
xyx+y=n, |x-y||x+y|=n,
hence xy=d|x-y|=d and x+y=nd|x+y|=\frac{n}{d}, where dd is a divisor of nn. The system
{xy=dx+y=nd \left\{\begin{array}{l} |x-y|=d \\ |x+y|=\frac{n}{d} \end{array}\right.
has four solutions, hence we have an=4τ(n)a_{n}=4 \tau(n), where τ(n)\tau(n) is the number of divisors of nn.

Case 2: n=4k+2n=4k+2. In this case x2y2(mod4)x^{2} \equiv y^{2} (\bmod 4), that is
x2y20(mod4), x^{2}-y^{2} \equiv 0 \quad(\bmod 4),
giving an=0a_{n}=0.

Case 3: n=2s(2k+1), s2n=2^{s}(2k+1),\ s \geq 2. The system (1) has no solutions when d2k+1d \mid 2k+1 or nd2k+1\left.\frac{n}{d} \right\rvert\, 2k+1. It follows that
an=4(τ(n)2τ(2k+1)). a_{n}=4(\tau(n)-2 \tau(2k+1)) .
Assume that n=2sp1α1ptαtn=2^{s} p_{1}^{\alpha_{1}} \ldots p_{t}^{\alpha_{t}}, where p1,,ptp_{1}, \ldots, p_{t} are odd primes. Then,
an=4((s+1)(α1+1)(αt+1)2(α1+1)(αt+1))=4(s1)(α1+1)(αt+1)=4τ(n4) \begin{aligned} a_{n} & =4\left((s+1)\left(\alpha_{1}+1\right) \ldots\left(\alpha_{t}+1\right)-2\left(\alpha_{1}+1\right) \ldots\left(\alpha_{t}+1\right)\right) \\ & =4(s-1)\left(\alpha_{1}+1\right) \ldots\left(\alpha_{t}+1\right) \\ & =4 \tau\left(\frac{n}{4}\right) \end{aligned}
Finally, we get
an={4τ(n) if n is odd 0 if n=4k+24τ(n4) if n=2s(2k+1), s2. a_{n}= \begin{cases}4 \tau(n) & \text{ if } n \text{ is odd } \\ 0 & \text{ if } n=4k+2 \\ 4 \tau\left(\frac{n}{4}\right) & \text{ if } n=2^{s}(2k+1),\ s \geq 2 .\end{cases}

For n=1432=23179n=1432=2^{3} \cdot 179, we have a1432=4τ(2179)=16a_{1432}=4 \tau(2 \cdot 179)=16. For n=1433n=1433, we have a1433=4τ(1433)=8a_{1433}=4 \tau(1433)=8, since 14331433 is a prime.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.