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 $d = \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 $d > 1$.
The condition $d > 1$ means that $n^2+3$ and $n+5$ share a common prime factor.
Let $p$ be a prime divisor of $d$.
Then $p \mid (n^2+3)$ and $p \mid (n+5)$.
From $p \mid (n+5)$, we have $n \equiv -5 \pmod p$.
Substituting this into the first congruence:
$n^2+3 \equiv (-5)^2 + 3 \equiv 25 + 3 \equiv 28 \equiv 0 \pmod p$.
So, $p$ must divide 28.
The prime factors of 28 are 2 and 7.
Thus, the only possible prime factors of $d$ are 2 and 7.
This means $d$ can be a divisor of 28.
Specifically, $d$ must be a multiple of 2 or 7 (or both).
So $d > 1$ if and only if $d$ is divisible by 2 or $d$ is divisible by 7.
Let's analyze the conditions for $d$ to be divisible by 2 and 7.

Case 1: $d$ is divisible by 2.
This means $\gcd(n^2+3, n+5)$ is even.
This implies $n^2+3$ is even and $n+5$ is even.
$n+5$ is even $\iff n$ is odd.
If $n$ is odd, $n^2$ is odd, so $n^2+3$ is even.
So, $d$ is divisible by 2 if and only if $n$ is odd.
Let $S_2$ be the set of integers $n \in \{1, \dots, 2025\}$ such that $2 \mid d$.
$S_2 = \{n \in \{1, \dots, 2025\} : n \text{ is odd}\}$.
The number of such integers is $\lceil 2025/2 \rceil = 1013$.
Wait, let's check.
$n$ is odd means $n \in \{1, 3, 5, \dots, 2025\}$.
The number of terms is $(2025 - 1)/2 + 1 = 1012 + 1 = 1013$.
So $|S_2| = 1013$.

Case 2: $d$ is divisible by 7.
This means $\gcd(n^2+3, n+5)$ is divisible by 7.
This implies $n^2+3 \equiv 0 \pmod 7$ and $n+5 \equiv 0 \pmod 7$.
From $n+5 \equiv 0 \pmod 7$, we have $n \equiv -5 \equiv 2 \pmod 7$.
Let's check if this satisfies the first condition.
$n^2+3 \equiv 2^2 + 3 = 4 + 3 = 7 \equiv 0 \pmod 7$.
Yes, it does.
So, $d$ is divisible by 7 if and only if $n \equiv 2 \pmod 7$.
Let $S_7$ be the set of integers $n \in \{1, \dots, 2025\}$ such that $7 \mid d$.
$S_7 = \{n \in \{1, \dots, 2025\} : n \equiv 2 \pmod 7\}$.
The integers are $2, 9, 16, \dots$.
The general form is $n = 7k + 2$.
We need $1 \le 7k + 2 \le 2025$.
$-1 \le 7k \le 2023$.
$0 \le k \le 2023/7$.
$2023 / 7 = 289$.
So $k$ can range from $0$ to $289$.
The number of values for $k$ is $289 - 0 + 1 = 290$.
So $|S_7| = 290$.

We want to find the number of $n$ such that $d > 1$.
This is equivalent to $n \in S_2 \cup S_7$.
By the Principle of Inclusion-Exclusion, $|S_2 \cup S_7| = |S_2| + |S_7| - |S_2 \cap S_7|$.
We need to find the size of the intersection $S_2 \cap S_7$.
$n \in S_2 \cap S_7$ means $n$ is odd AND $n \equiv 2 \pmod 7$.
$n \equiv 2 \pmod 7$ implies $n$ can be written as $7k + 2$.
For $n$ to be odd, $7k + 2$ must be odd.
Since 2 is even, $7k$ must be odd.
Since 7 is odd, $k$ must be odd.
So we need to count the number of odd integers $k$ such that $0 \le k \le 289$.
The possible values for $k$ are $1, 3, 5, \dots, 289$.
This is an arithmetic progression with first term 1, last term 289, and common difference 2.
Let $m$ be the number of terms.
$289 = 1 + (m-1)2 \implies 288 = 2(m-1) \implies 144 = m-1 \implies m = 145$.
Alternatively, the number of odd integers in $\{0, \dots, 289\}$ is $\lceil 290/2 \rceil = 145$.
Wait, the range of $k$ is $0, 1, \dots, 289$. Total 290 values.
Half are even, half are odd?
$0$ is even. $289$ is odd.
The sequence is $0, 1, 2, \dots, 289$.
Evens: $0, 2, \dots, 288$. Number of terms is $288/2 + 1 = 145$.
Odds: $1, 3, \dots, 289$. Number of terms is $(289-1)/2 + 1 = 145$.
So $|S_2 \cap S_7| = 145$.

Let's double check this.
$n \in S_2 \cap S_7 \iff n \equiv 1 \pmod 2$ and $n \equiv 2 \pmod 7$.
By Chinese Remainder Theorem, since $\gcd(2, 7) = 1$, there is a unique solution modulo 14.
$n \equiv 2 \pmod 7 \implies n \in \{2, 9, 16, \dots\}$.
$n \equiv 1 \pmod 2 \implies n$ is odd.
$2$ is even.
$9$ is odd.
$16$ is even.
So $n \equiv 9 \pmod{14}$.
Let's check: $9 \equiv 1 \pmod 2$ and $9 \equiv 2 \pmod 7$. Correct.
So we need to count $n \in \{1, \dots, 2025\}$ such that $n \equiv 9 \pmod{14}$.
$n = 14j + 9$.
$1 \le 14j + 9 \le 2025$.
$-8 \l