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.

I need to find the number of integers $n$ with $1 \le n \le 2025$ such that $\gcd(n^2 + 3, n + 5) > 1$.

Let me denote $d = \gcd(n^2 + 3, n + 5)$.

Since $d$ divides both $n^2 + 3$ and $n + 5$, it must also divide any linear combination of these expressions.

I'll use the property that if $d | a$ and $d | b$, then $d | (a \cdot k_1 + b \cdot k_2)$ for any integers $k_1, k_2$.

Let me find a useful linear combination. Since $d | (n^2 + 3)$ and $d | (n + 5)$, I can compute:
$d | (n^2 + 3) - (n + 5)(n - 5) = n^2 + 3 - (n^2 - 25) = n^2 + 3 - n^2 + 25 = 28$

So $d | 28$.

Since $28 = 2^2 \cdot 7$, the possible values of $d$ are: $1, 2, 4, 7, 14, 28$.

But we want $d > 1$, so $d \in \{2, 4, 7, 14, 28\}$.

Now I need to determine when $\gcd(n^2 + 3, n + 5) = d$ for each possible $d$.

Let me work with the Euclidean algorithm approach more systematically.

Since $\gcd(n^2 + 3, n + 5) = \gcd(n + 5, (n^2 + 3) \bmod (n + 5))$.

To compute $(n^2 + 3) \bmod (n + 5)$:
$n^2 + 3 = (n + 5)(n - 5) + 28$

This is because $(n + 5)(n - 5) = n^2 - 25$, so:
$n^2 + 3 = n^2 - 25 + 28 = (n + 5)(n - 5) + 28$

Therefore: $\gcd(n^2 + 3, n + 5) = \gcd(n + 5, 28)$

So I need to find when $\gcd(n + 5, 28) > 1$.

Since $28 = 2^2 \cdot 7$, we have $\gcd(n + 5, 28) > 1$ if and only if $n + 5$ shares a prime factor with 28.

This happens when $n + 5$ is divisible by 2 or 7 (or both).

In other words, $\gcd(n + 5, 28) > 1$ if and only if $n + 5 \equiv 0 \pmod{2}$ or $n + 5 \equiv 0 \pmod{7}$.

This is equivalent to:
- $n \equiv 1 \pmod{2}$ (since $n + 5 \equiv 0 \pmod{2}$ means $n \equiv 1 \pmod{2}$)
- $n \equiv 2 \pmod{7}$ (since $n + 5 \equiv 0 \pmod{7}$ means $n \equiv 2 \pmod{7}$)

So I want the count of integers $n$ with $1 \le n \le 2025$ such that:
$n \equiv 1 \pmod{2}$ OR $n \equiv 2 \pmod{7}$

Using inclusion-exclusion principle:
Let $A = \{n : 1 \le n \le 2025, n \equiv 1 \pmod{2}\}$
Let $B = \{n : 1 \le n \le 2025, n \equiv 2 \pmod{7}\}$

$|A|$: Numbers $\equiv 1 \pmod{2}$ in range $[1, 2025]$
These are odd numbers: $1, 3, 5, \ldots, 2025$
Count = $\frac{2025 - 1}{2} + 1 = 1013$

$|B|$: Numbers $\equiv 2 \pmod{7}$ in range $[1, 2025]$
These are: $2, 9, 16, \ldots, 2023$
The largest such number $\le 2025$ is found by solving $2 + 7k \le 2025$, so $7k \le 2023$, so $k \le 289$.
Count = $289 + 1 = 290$

$|A \cap B|$: Numbers $\equiv 1 \pmod{2}$ AND $\equiv 2 \pmod{7}$
By the Chinese Remainder Theorem, since $\gcd(2,7) = 1$, this is equivalent to $n \equiv x \pmod{14}$ for some $x$.
We need $n \equiv 1 \pmod{2}$ and $n \equiv 2 \pmod{7}$.
From the second congruence: $n = 7k + 2$
Substituting into first: $7k + 2 \equiv 1 \pmod{2}$
$7k \equiv -1 \equiv 1 \pmod{2}$
$k \equiv 1 \pmod{2}$ (since $7 \equiv 1 \pmod{2}$)
So $k = 2j + 1$, which gives $n = 7(2j + 1) + 2 = 14j + 9$
Therefore: $n \equiv 9 \pmod{14}$

Count of such numbers in range $[1, 2025]$:
We want $1 \le 14j + 9 \le 2025$, so $-8 \le 14j \le 2016$, so $0 \le j \le 144$.
Count = $144 + 1 = 145$

By inclusion-exclusion:
$|A \cup B| = |A| + |B| - |A \cap B| = 1013 + 290 - 145 = 1158$

$\boxed{1158}$