Number theoryDifficulty 5.8AIME, harderProve itSaudi Arabia
For any positive integer n let an be the number of pairs (x,y) of integers satisfying ∣x2−y2∣=n.
a. Find a1432 and a1433.
b. Find an.
Solution
Let us consider the following cases.
Case 1: n is odd. The equation ∣x2−y2∣=n is equivalent to ∣x−y∣∣x+y∣=n, hence ∣x−y∣=d and ∣x+y∣=dn, where d is a divisor of n. The system {∣x−y∣=d∣x+y∣=dn has four solutions, hence we have an=4τ(n), where τ(n) is the number of divisors of n.
Case 2: n=4k+2. In this case x2≡y2(mod4), that is x2−y2≡0(mod4), giving an=0.
Case 3: n=2s(2k+1),s≥2. The system (1) has no solutions when d∣2k+1 or dn2k+1. It follows that an=4(τ(n)−2τ(2k+1)). Assume that n=2sp1α1…ptαt, where p1,…,pt are odd primes. Then, an=4((s+1)(α1+1)…(αt+1)−2(α1+1)…(αt+1))=4(s−1)(α1+1)…(αt+1)=4τ(4n) Finally, we get an=⎩⎨⎧4τ(n)04τ(4n) if n is odd if n=4k+2 if n=2s(2k+1),s≥2.
For n=1432=23⋅179, we have a1432=4τ(2⋅179)=16. For n=1433, we have a1433=4τ(1433)=8, since 1433 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.