Let an be the number of distinct prime divisors of a positive integer n > 1. For example, a8 = 1 since 8 has only one prime divisor, namely 2, a13 = 1, and a30 = 3 since 30 has the three prime divisors 2, 3 and 5. Define S to be the set of all pairs of positive integers (m, n) such that m 6= n and am+n = am + an. Show that the set S is infinite.

To prove that the set \( S \) of all pairs of positive integers \( (m, n) \) such that \( m \neq n \) and \( a_{m+n} = a_m + a_n \) is infinite, we'll construct an infinite subset of \( S \) by considering pairs of the form \( (p^k, p^l) \), where \( p \) is a prime number and \( k, l \) are distinct positive integers.

### Step 1: Calculate \( a_m \), \( a_n \), and \( a_{m+n} \)
Consider \( m = p^k \) and \( n = p^l \), where \( p \) is a prime and \( k \) and \( l \) are distinct positive integers. For any positive integer power of a prime number, the number of distinct prime divisors is always 1. Therefore:
\[
a_m = a_{p^k} = 1
\]
\[
a_n = a_{p^l} = 1
\]

Now, let's calculate \( a_{m+n} = a_{p^k + p^l} \).

### Step 2: Analyze \( m+n = p^k + p^l \)
Without loss of generality, assume \( k < l \). We can factor \( p^k + p^l \) as:
\[
p^k + p^l = p^k(1 + p^{l-k})
\]
Here, \( p^k \) contributes exactly one prime factor, which is \( p \). The term \( 1 + p^{l-k} \) is an integer greater than 1. Since \( l-k \) is a positive integer, \( 1 + p^{l-k} \) is not divisible by \( p \). Therefore, \( 1 + p^{l-k} \) and \( p^k \) are coprime.

Since \( 1 + p^{l-k} \) is not divisible by \( p \) and does not introduce any new prime divisors, \( p^k + p^l \) has exactly two distinct prime divisors: \( p \) from the \( p^k \) term and whatever prime divides \( 1 + p^{l-k} \) (note that \( 1 + p^{l-k} \) is not divisible by \( p \), and thus must be divisible by some other prime).

Therefore:
\[
a_{m+n} = a_{p^k + p^l} = 2
\]

### Step 3: Check the condition \( a_{m+n} = a_m + a_n \)
We already know that:
\[
a_m = 1, \quad a_n = 1
\]
\[
a_{m+n} = 2
\]
Thus:
\[
a_{m+n} = 2 = 1 + 1 = a_m + a_n
\]
So, \( (m, n) = (p^k, p^l) \) satisfies the condition \( a_{m+n} = a_m + a_n \).

### Step 4: Infinite Set \( S \)
Since there are infinitely many primes \( p \), and for each prime \( p \), we can choose infinitely many distinct pairs of positive integers \( k \) and \( l \) with \( k \neq l \), we can generate infinitely many pairs \( (m, n) = (p^k, p^l) \) such that \( a_{m+n} = a_m + a_n \).

Therefore, the set \( S \) is infinite.

### Conclusion
We have shown that \( S \), the set of all pairs of positive integers \( (m, n) \) such that \( m \neq n \) and \( a_{m+n} = a_m + a_n \), is infinite.

Do you have any questions, or would you like further details?

Here are some related questions for further exploration:
1. What happens if \( m \) and \( n \) are not powers of the same prime? 
2. How does the condition \( a_{m+n} = a_m + a_n \) change for composite numbers?
3. What is the smallest pair \( (m, n) \) that belongs to the set \( S \)?
4. Can we generalize this problem for higher powers

Explore the proof demonstrating an infinite set of pairs (m, n) such that m ≠ n and am+n = am + an, where am is the count of distinct prime divisors of the integer n > 1. This mathematical problem involves number theory and the properties of prime divisors. Suitable for advanced high school students and beyond.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation