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.

We are given the expression:

$$
\gcd(n^2 + 3, \, n + 5) > 1
$$

and asked to find how many integers $ n $ with $ 1 \le n \le 2025 $ satisfy this condition.

---

### Step 1: Use Euclidean Algorithm

Recall that:

$$
\gcd(a, b) = \gcd(b, a \bmod b)
$$

Let:
- $ a = n^2 + 3 $
- $ b = n + 5 $

We compute $ n^2 + 3 \mod (n + 5) $. To do this, perform polynomial division or use substitution.

Let’s write $ n \equiv -5 \pmod{n+5} $. So substitute $ n = -5 $ into $ n^2 + 3 $ to find the remainder:

$$
n^2 + 3 \equiv (-5)^2 + 3 = 25 + 3 = 28 \pmod{n+5}
$$

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

Thus, the gcd is greater than 1 **iff** $ \gcd(n + 5, 28) > 1 $, i.e., $ n + 5 $ shares a common factor with 28 greater than 1.

So we want:

$$
\gcd(n + 5, 28) > 1
$$

Let’s factor 28:

$$
28 = 2^2 \cdot 7
$$

So the positive divisors of 28 are: $ 1, 2, 4, 7, 14, 28 $. So $ \gcd(n+5, 28) > 1 $ means $ n + 5 $ is divisible by **2 or 7** (i.e., not coprime to 28).

So we want to count how many integers $ n $ in $ [1, 2025] $ such that $ n + 5 $ is divisible by 2 or 7.

Let’s define $ m = n + 5 $. Then:

- When $ n = 1 $, $ m = 6 $
- When $ n = 2025 $, $ m = 2030 $

So $ m $ ranges from 6 to 2030 inclusive.

We want to count how many integers $ m \in [6, 2030] $ such that $ \gcd(m, 28) > 1 $, i.e., $ m $ divisible by 2 or 7.

Let’s compute:

- Total numbers in range: $ 2030 - 6 + 1 = 2025 $ (as expected)
- Count numbers **not** divisible by 2 or 7 → i.e., coprime to 28? Not exactly — just not divisible by 2 or 7. Since 28's prime factors are only 2 and 7, being coprime to 28 is equivalent to not divisible by 2 or 7.

So we want:

$$
\#(m \in [6,2030] : 2 \nmid m \text{ and } 7 \nmid m)
$$

Then subtract from total to get desired count.

Let’s compute using inclusion-exclusion.

Let:
- $ A $ = numbers divisible by 2
- $ B $ = numbers divisible by 7

We want $ |A \cup B| = |A| + |B| - |A \cap B| $

Where:
- $ |A| $ = number of multiples of 2 in [6, 2030]
- $ |B| $ = number of multiples of 7 in [6, 2030]
- $ |A \cap B| $ = multiples of lcm(2,7) = 14

Compute each:

#### Multiples of 2:

Smallest multiple of 2 ≥ 6 is 6  
Largest ≤ 2030 is 2030

Number: $ \frac{2030 - 6}{2} + 1 = \frac{2024}{2} + 1 = 1012 + 1 = 1013 $

Alternatively, count multiples of 2 from 1 to 2030 minus those from 1 to 5:

- $ \lfloor 2030/2 \rfloor = 1015 $
- $ \lfloor 5/2 \rfloor = 2 $
- So $ 1015 - 2 = 1013 $ ✅

#### Multiples of 7:

Smallest multiple of 7 ≥ 6 is 7  
Largest ≤ 2030: $ \lfloor 2030/7 \rfloor = ? $

Compute $ 7 \times 290 = 2030 $ exactly? Let's check: $ 7 \times 290 = 2030 $. Yes!

So largest is 2030.

Number of multiples from 1 to 2030: $ \lfloor 2030/7 \rfloor = 290 $

Multiples ≤5: $ \lfloor 5/7 \rfloor = 0 $

So total: $ 290 - 0 = 290 $

#### Multiples of 14:

Smallest multiple of 14 ≥6 is 14  
Largest ≤2030: $ \lfloor 2030/14 \rfloor = ? $

$ 14 \times 145 = 2030 $? Let's check: $ 14 \times 100 = 1400 $, $ 14 \times 45 = 630 $, sum = 2030. Yes!

So largest is 2030.

Multiples from 1 to 2030: $ \lfloor 2030/14 \rfloor = 145 $

Multiples ≤5: $ \lfloor 5/14 \rfloor = 0 $

So total: $ 145 $

Thus:

$$
|A \cup B| = 1013 + 290 - 145 = 1158
$$

Wait: $1013 + 290 = 1303$, minus 145 = **1158**

So there are **1158** values of $ m \in [6,2030] $ divisible by 2 or 7.

Therefore, the number of $ n \in [1,2025] $ such that $ \gcd(n^2+3, n+5) > 1 $ is **1158**.

But wait — double-check: Is it possible that $ \gcd(n+5, 28) > 1 $ but the gcd could be something else? No — we already established:

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

So the condition is exactly that $ \gcd(n+5, 28) > 1 $, i.e., $ n+5 $ shares a prime factor with 28: 2 or 7.

Thus, answer is **1158**.

But let’s double-check the arithmetic:

- Total numbers: 2025
- Count of numbers where $ \gcd = 1 $: numbers where $ n+5 $ is coprime to 28 → not divisible by 2 or 7.

Let’s compute that count directly and subtract from 2025.

We want numbers $ m \in [6,2030] $ such that $ m \not\equiv 0 \