math-nt-01

# Sharing a Factor

For how many integers $n$ with $1 \le n \le 2025$ is
$$\gcd\!\left(n^{2}+3,\; n+5\right) > 1?$$

Give your final answer as a single integer.

Let $g(n) = \gcd(n^2+3, n+5)$. We want to find the number of integers $n$ in the range $1 \le n \le 2025$ such that $g(n) > 1$.

Let $d = \gcd(n^2+3, n+5)$.
By the properties of the gcd, $d$ must divide any linear combination of the two numbers.
Specifically, $d$ divides $(n^2+3) - n(n+5)$.
Let's compute this:
$n^2+3 - n(n+5) = n^2+3 - n^2 - 5n = 3 - 5n$.
So $d$ divides $3-5n$.
Also, $d$ divides $n+5$.
Since $d$ divides $n+5$, it must divide $5(n+5) = 5n+25$.
Since $d$ divides $3-5n$, it must divide $(3-5n) + (5n+25) = 28$.
So $d$ must be a divisor of 28.
The divisors of 28 are 1, 2, 4, 7, 14, 28.
We are looking for $n$ such that $g(n) > 1$. This means $d$ must be one of $\{2, 4, 7, 14, 28\}$.
So $g(n) > 1$ if and only if $g(n)$ divides 28 and $g(n) \neq 1$.
This is equivalent to saying that $\gcd(n^2+3, n+5)$ divides 28 and is greater than 1.
Wait, let's rephrase.
$g(n) = \gcd(n^2+3, n+5)$.
We found that $g(n)$ divides 28.
So $g(n) \in \{1, 2, 4, 7, 14, 28\}$.
We want to count $n$ such that $g(n) \neq 1$.
This is equivalent to counting $n$ such that $\gcd(n^2+3, n+5) > 1$.
Since $g(n)$ divides 28, $g(n) > 1$ means $g(n)$ shares a common factor with 28.
Actually, $g(n)$ is a divisor of 28. So $g(n) > 1$ is equivalent to saying that $n^2+3$ and $n+5$ are not coprime.
Let's analyze the condition $g(n) > 1$.
Since $g(n)$ divides 28, $g(n) > 1$ implies that $g(n)$ is divisible by some prime factor of 28.
The prime factors of 28 are 2 and 7.
So $g(n) > 1$ if and only if $\gcd(n^2+3, n+5)$ is divisible by 2 or 7.
This is equivalent to:
$(n^2+3 \equiv 0 \pmod p \text{ and } n+5 \equiv 0 \pmod p)$ for some $p \in \{2, 7\}$.
Let's check this logic.
If $\gcd(A, B) > 1$, then there exists a prime $p$ such that $p | \gcd(A, B)$, which means $p|A$ and $p|B$.
Here $A = n^2+3$ and $B = n+5$.
So we need to find $n$ such that there exists a prime $p \in \{2, 7\}$ where $n+5 \equiv 0 \pmod p$ and $n^2+3 \equiv 0 \pmod p$.
Note that if $p | \gcd(n^2+3, n+5)$, then $p$ must divide 28.
So the possible primes are indeed 2 and 7.
Let's check if there are any other primes.
We established $d | 28$. So any common divisor must be a divisor of 28.
Thus, any prime factor of $d$ must be a prime factor of 28.
The prime factors of 28 are 2 and 7.
So we just need to count $n$ such that $2 | \gcd(n^2+3, n+5)$ or $7 | \gcd(n^2+3, n+5)$.
Let $S$ be the set of such $n$.
$S = \{n \in \{1, \dots, 2025\} : \gcd(n^2+3, n+5) > 1\}$.
$S = \{n \in \{1, \dots, 2025\} : \exists p \in \{2, 7\}, p | (n^2+3) \text{ and } p | (n+5)\}$.
Let $S_2 = \{n \in \{1, \dots, 2025\} : 2 | (n^2+3) \text{ and } 2 | (n+5)\}$.
Let $S_7 = \{n \in \{1, \dots, 2025\} : 7 | (n^2+3) \text{ and } 7 | (n+5)\}$.
We want to find $|S_2 \cup S_7| = |S_2| + |S_7| - |S_2 \cap S_7|$.

Let's analyze $S_2$.
Condition: $2 | (n+5)$ and $2 | (n^2+3)$.
$n+5 \equiv 0 \pmod 2 \implies n \equiv -5 \equiv 1 \pmod 2$.
$n^2+3 \equiv 1^2+3 = 4 \equiv 0 \pmod 2$.
So if $n$ is odd, then $n+5$ is even and $n^2+3$ is even.
Thus, $2 | \gcd(n^2+3, n+5)$ is equivalent to $n$ being odd.
So $S_2$ is the set of odd integers in $\{1, \dots, 2025\}$.
The number of odd integers in this range is $\lceil 2025/2 \rceil = 1013$.
Wait, let's verify.
If $n$ is even, $n+5$ is odd, so $\gcd$ is odd.
If $n$ is odd, $n+5$ is even, $n^2$ is odd, $n^2+3$ is even. So $\gcd$ is even.
So $S_2$ is exactly the set of odd $n$.
Number of elements in $S_2$ is 1013.

Now let's analyze $S_7$.
Condition: $7 | (n+5)$ and $7 | (n^2+3)$.
$n+5 \equiv 0 \pmod 7 \implies n \equiv -5 \equiv 2 \pmod 7$.
Let's check if $n \equiv 2 \pmod 7$ implies $7 | (n^2+3)$.
$n^2+3 \equiv 2^2+3 = 4+3 = 7 \equiv 0 \pmod 7$.
Yes, it does.
So $S_7$ is the set of integers $n$ such that $n \equiv 2 \pmod 7$.
We need to count how many such $n$ are in $\{1, \dots, 2025\}$.
The values are $2, 9, 16, \dots$.
The general form is $n = 7k + 2$.
We need $1 \le 7k+2 \le 2025$.
$7k \ge -1 \implies k \ge 0$ (since $k$ is integer, $k \ge -1/7$).
$7k \le 2023 \implies k \le 2023/7$.
$2023 /