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.

Alright, I have this problem:

**Problem Statement:**  
For how many integers \( n \) with \( 1 \le n \le 2025 \) is  
\[ \gcd\!\left(n^{2}+3,\; n+5\right) > 1? \]

### Understanding the Problem
First, I need to find all integers \( n \) from 1 to 2025 such that the greatest common divisor (gcd) of \( n^2 + 3 \) and \( n + 5 \) is greater than 1.

### Approach
The gcd of two numbers \( a \) and \( b \) is greater than 1 if they share any common prime factor. So, I need to find all \( n \) such that \( n^2 + 3 \) and \( n + 5 \) have a common prime factor.

### Using the Euclidean Algorithm
The Euclidean algorithm can help simplify the gcd condition. The gcd of \( n^2 + 3 \) and \( n + 5 \) can be related to the gcd of \( n^2 + 3 \) and \( (n^2 + 3) - (n + 5)(n - 5) \).

Let's compute \( (n + 5)(n - 5) \):
\[ (n + 5)(n - 5) = n^2 - 25 \]

Now, subtract this from \( n^2 + 3 \):
\[ n^2 + 3 - (n^2 - 25) = 28 \]

So, according to the Euclidean algorithm:
\[ \gcd(n^2 + 3, n + 5) = \gcd(n + 5, 28) \]

### Simplifying the Condition
The condition \( \gcd(n^2 + 3, n + 5) > 1 \) is equivalent to \( \gcd(n + 5, 28) > 1 \).

### Finding Common Divisors
The number 28 has prime factors 2 and 7. So, \( \gcd(n + 5, 28) > 1 \) means that \( n + 5 \) must share a common factor with 28, i.e., \( n + 5 \) must be divisible by 2 or 7.

### Case 1: \( n + 5 \) is divisible by 2
This means \( n \) must be odd because:
\[ n + 5 \equiv 0 \mod 2 \implies n \equiv 1 \mod 2 \]

### Case 2: \( n + 5 \) is divisible by 7
This means:
\[ n + 5 \equiv 0 \mod 7 \implies n \equiv 2 \mod 7 \]

### Combining Both Cases
The condition \( \gcd(n + 5, 28) > 1 \) is satisfied if \( n \) is odd or \( n \equiv 2 \mod 7 \).

But we need to be careful about double-counting numbers that satisfy both conditions.

### Total Numbers
First, find the total number of integers \( n \) from 1 to 2025.

1. **Total numbers**: 2025.

2. **Numbers not satisfying the condition**: \( \gcd(n + 5, 28) = 1 \).

But it's easier to find numbers that satisfy the condition.

#### Using Inclusion-Exclusion Principle
- **Numbers divisible by 2**: \( n \) is odd.
  - Total odd numbers from 1 to 2025: \( \frac{2025 + 1}{2} = 1013 \).

- **Numbers divisible by 7**: \( n \equiv 2 \mod 7 \).
  - The smallest \( n \) is 2 (since \( 2 + 5 = 7 \)).
  - The largest \( n \) is \( 7k - 5 \leq 2025 \implies k \leq \frac{2030}{7} \approx 290 \).
  - So, \( k \) ranges from 1 to 290.
  - Total numbers: 290.

But we need to find numbers that are divisible by both 2 and 7, i.e., divisible by 14.

- **Numbers divisible by 14**: \( n \equiv 9 \mod 14 \) (since \( n + 5 \equiv 0 \mod 14 \implies n \equiv 9 \mod 14 \)).
  - The smallest \( n \) is 9.
  - The largest \( n \) is \( 14k - 5 \leq 2025 \implies k \leq \frac{2030}{14} \approx 145 \).
  - So, \( k \) ranges from 1 to 145.
  - Total numbers: 145.

But according to the inclusion-exclusion principle, the total numbers satisfying either condition is:
\[ \text{Odd numbers} + \text{Numbers divisible by 7} - \text{Numbers divisible by 14} \]
\[ 1013 + 290 - 145 = 1158 \]

But, is this correct? Let's verify.

### Verification
The condition is \( \gcd(n + 5, 28) > 1 \), which is equivalent to \( n + 5 \) being divisible by 2 or 7.

- **Divisible by 2**: \( n \) is odd.
- **Divisible by 7**: \( n \equiv 2 \mod 7 \).

But, numbers divisible by both 2 and 7 are divisible by 14.

- **Divisible by 14**: \( n \equiv 9 \mod 14 \).

But, the condition is \( n \) is odd or \( n \equiv 2 \mod 7 \).

- **Odd numbers**: 1013.
- **Numbers \( n \equiv 2 \mod 7 \)**: 290.
- **Numbers \( n \equiv 9 \mod 14 \)**: 145.

But, numbers \( n \equiv 9 \mod 14 \) are a subset of both odd numbers and numbers \( n \equiv 2 \mod 7 \).

- **Numbers \( n \equiv 2 \mod 7 \) and odd**: 
  - \( n \equiv 2 \mod 7 \) and \( n \equiv 1 \mod 2 \).
  - Using Chinese Remainder Theorem, \( n \equiv 9 \mod 14 \) (since \( 9 \mod 14 \) satisfies both \( 9 \equiv 2 \mod 7 \) and \( 9 \equiv 1 \mod 2 \)).