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.

To determine how many integers \( n \) with \( 1 \le n \le 2025 \) satisfy \( \gcd(n^2 + 3, n + 5) > 1 \), we use the Euclidean algorithm. 

First, we compute:
\[
\gcd(n^2 + 3, n + 5) = \gcd(n + 5, (n^2 + 3) \mod (n + 5))
\]
Performing polynomial division, we find:
\[
n^2 + 3 = (n + 5)(n - 5) + 28
\]
Thus, the remainder is 28, so:
\[
\gcd(n^2 + 3, n + 5) = \gcd(n + 5, 28)
\]
For this gcd to be greater than 1, \( n + 5 \) must share a common factor with 28. The prime factors of 28 are 2 and 7. Therefore, \( n + 5 \) must be divisible by 2 or 7.

We calculate the number of such \( n \) using inclusion-exclusion principle:

1. **Numbers where \( n + 5 \) is even (divisible by 2):**  
   \( n \) must be odd. There are \( \left\lfloor \frac{2025 + 1}{2} \right\rfloor = 1013 \) such numbers.

2. **Numbers where \( n + 5 \) is divisible by 7:**  
   \( n \equiv 2 \pmod{7} \). The count is \( \left\lfloor \frac{2025 - 2}{7} \right\rfloor + 1 = 289 + 1 = 290 \).

3. **Numbers where \( n + 5 \) is divisible by both 2 and 7 (i.e., 14):**  
   \( n \equiv 9 \pmod{14} \). The count is \( \left\lfloor \frac{2025 - 9}{14} \right\rfloor + 1 = 144 + 1 = 145 \).

Using inclusion-exclusion:
\[
1013 + 290 - 145 = 1158
\]
However, upon re-evaluating the count of numbers divisible by 7, we find it should be 289, not 290. Thus, the correct total is:
\[
1013 + 289 - 145 = 1157
\]

The final answer is:
\[
\boxed{1157}
\]