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 the number of integers \( n \) such that \( \gcd(n^2 + 3, n + 5) > 1 \) for \( 1 \le n \le 2025 \), we start by analyzing the expression \( \gcd(n^2 + 3, n + 5) \).

Let \( d = \gcd(n^2 + 3, n + 5) \). By the properties of the greatest common divisor, \( d \) must divide any linear combination of \( n^2 + 3 \) and \( n + 5 \). In particular, \( d \) must divide:

\[
d \mid (n^2 + 3) - n(n + 5) = n^2 + 3 - n^2 - 5n = 3 - 5n
\]

Thus, \( d \mid 3 - 5n \). Therefore, \( d \) must be a divisor of \( 3 - 5n \).

We need to find when \( d > 1 \). The divisors of 3 are 1 and 3. Hence, \( d \) can be 1 or 3. We seek the cases where \( d = 3 \).

For \( d = 3 \), we have:

\[
3 \mid 3 - 5n \implies 3 \mid 5n - 3
\]

This simplifies to:

\[
3 \mid 5n - 3 \implies 3 \mid 5n - 3
\]

Since 3 divides \( 5n - 3 \), we can write:

\[
5n \equiv 3 \pmod{3}
\]

Reducing \( 5n \mod 3 \):

\[
5 \equiv 2 \pmod{3} \implies 5n \equiv 2n \pmod{3}
\]

Thus:

\[
2n \equiv 3 \pmod{3} \implies 2n \equiv 0 \pmod{3} \implies n \equiv 0 \pmod{3}
\]

So, \( n \) must be a multiple of 3. We need to count how many multiples of 3 are there in the range from 1 to 2025.

The multiples of 3 in this range are \( 3, 6, 9, \ldots, 2025 \). This is an arithmetic sequence where the first term \( a = 3 \) and the common difference \( d = 3 \). The general term of this sequence is given by:

\[
a_k = 3k
\]

We need to find the largest \( k \) such that \( 3k \le 2025 \):

\[
3k \le 2025 \implies k \le 675
\]

Thus, there are 675 multiples of 3 in this range. Therefore, there are 675 integers \( n \) for which \( \gcd(n^2 + 3, n + 5) = 3 \).

Hence, the final answer is:

\[
\boxed{675}
\]