+0

# difficult math competition problem

0
89
1

Given the expression (n^2−9)/(n2−4), for how many positive integers n from 1 to 2016, inclusive, is the GCF of the numerator and denominator greater than 1?

ive started by factoring into (n-3)(n+3)/(n-2)(n+2) but have no idea how to go from there

Jan 6, 2023

#1
0

You can rewrite this as:

(n−3)(n+3)(n−2)(n+2)

Consecutive integers are always coprime, so there are no common factors of n−2 and n−3 or n+2 and n+3 - so the question boils down to how many positive integers from 1 to 2016 have a common factor for n−2 and n+3 or n−3 and n+2 - and since the difference is 5, the only possible common factor can be 5.

In other words, we have a solution whenever n=2 or 3(mod5) - with the exception of n=2 which gives a division by 0. We start counting at n=3, since gcd(0,5)=5.

Let’s check n=7 and n=8 to gut-check the answer: gcd(7^2−9,7^2−4)=5 and gcd(8^2−9,8^2−4)=5 - all looks good! All solutions other than 3 are of the form 5k+2 or 5k+3 for 1≤k≤402 giving 805 possible solutions.

Jan 6, 2023