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 find the number of integers $n$ with $1 \le n \le 2025$ such that $\gcd(n^2+3, n+5) > 1$, we first simplify the expression for the greatest common divisor.

Let $d = \gcd(n^2+3, n+5)$. By the properties of the greatest common divisor, we have:
$$ \gcd(n^2+3, n+5) = \gcd(n^2+3 - n(n+5), n+5) $$
$$ = \gcd(n^2+3 - n^2 - 5n, n+5) $$
$$ = \gcd(-5n+3, n+5) $$
We can continue to eliminate $n$ from the first term:
$$ \gcd(-5n+3, n+5) = \gcd(-5n+3 + 5(n+5), n+5) $$
$$ = \gcd(-5n+3 + 5n + 25, n+5) $$
$$ = \gcd(28, n+5) $$
Thus, the condition $\gcd(n^2+3, n+5) > 1$ is equivalent to $\gcd(28, n+5) > 1$.
This means that $n+5$ must share a common factor with 28 greater than 1. The prime factorization of 28 is $2^2 \cdot 7$, so the prime factors are 2 and 7. Therefore, the condition is satisfied if and only if $n+5$ is divisible by 2 or $n+5$ is divisible by 7.

Let $m = n+5$. Since $1 \le n \le 2025$, the range for $m$ is $6 \le m \le 2030$.
We need to count the number of integers $m$ in the interval $[6, 2030]$ such that $m$ is divisible by 2 or $m$ is divisible by 7.
Let $A$ be the set of multiples of 2 in $[6, 2030]$, and $B$ be the set of multiples of 7 in $[6, 2030]$. We want to find $|A \cup B|$.
Using the Principle of Inclusion-Exclusion, $|A \cup B| = |A| + |B| - |A \cap B|$.

1.  **Count $|A|$**: The number of multiples of 2 in $[6, 2030]$.
    The multiples are $6, 8, \dots, 2030$.
    The number of terms is $\frac{2030 - 6}{2} + 1 = \frac{2024}{2} + 1 = 1012 + 1 = 1013$.
    Alternatively, using the floor function: $\lfloor \frac{2030}{2} \rfloor - \lfloor \frac{5}{2} \rfloor = 1015 - 2 = 1013$.

2.  **Count $|B|$**: The number of multiples of 7 in $[6, 2030]$.
    The multiples are $7, 14, \dots, 2030$.
    The number of terms is $\frac{2030 - 7}{7} + 1 = \frac{2023}{7} + 1 = 289 + 1 = 290$.
    Alternatively: $\lfloor \frac{2030}{7} \rfloor - \lfloor \frac{5}{7} \rfloor = 290 - 0 = 290$.

3.  **Count $|A \cap B|$**: The number of multiples of $\text{lcm}(2, 7) = 14$ in $[6, 2030]$.
    The multiples are $14, 28, \dots, 2030$.
    The number of terms is $\frac{2030 - 14}{14} + 1 = \frac{2016}{14} + 1 = 144 + 1 = 145$.
    Alternatively: $\lfloor \frac{2030}{14} \rfloor - \lfloor \frac{5}{14} \rfloor = 145 - 0 = 145$.

Now, we calculate the union:
$$ |A \cup B| = 1013 + 290 - 145 = 1303 - 145 = 1158 $$

Thus, there are 1158 integers $n$ in the given range satisfying the condition.

\boxed{1158}