Maths Olympiad Prep

Library / /19 of 27

Number theory Difficulty 6.5 National olympiad Find the answer

Find the number of pairs (a,b)(a, b) of positive integers with the property that the greatest common divisor of aa and b b is equal to 123...501\cdot 2 \cdot 3\cdot ... \cdot50, and the least common multiple of aa and b b is 122232...5021^2 \cdot 2^2 \cdot 3^2\cdot ... \cdot 50^2.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to examine the conditions given for the pairs (a,b)(a, b) of positive integers:
1. The greatest common divisor (GCD) of aa and bb is 123501 \cdot 2 \cdot 3 \cdot \ldots \cdot 50.
2. The least common multiple (LCM) of aa and bb is 1222325021^2 \cdot 2^2 \cdot 3^2 \cdot \ldots \cdot 50^2.

### Step 1: Express Conditions Using Prime Factorization

First, let's write both the GCD and LCM conditions using prime factorization.

Let P=12350 P = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot 50 .
The prime factorization of P P would be:
P=2p23p35p547p47 P = 2^{p_2} \cdot 3^{p_3} \cdot 5^{p_5} \cdot \ldots \cdot 47^{p_{47}}
where pk p_k is the power of the prime k k in the factorization of the numbers from 1 1 to 50 50 .

The LCM condition translates to:
LCM(a,b)=122232502=22p232p352p5472p47 \text{LCM}(a, b) = 1^2 \cdot 2^2 \cdot 3^2 \cdot \ldots \cdot 50^2 = 2^{2p_2} \cdot 3^{2p_3} \cdot 5^{2p_5} \cdot \ldots \cdot 47^{2p_{47}}

### Step 2: Relate GCD and LCM to (a,b)(a, b)

For (a,b)(a, b), we have:
- a=2a23a347a47 a = 2^{a_2} \cdot 3^{a_3} \cdot \ldots \cdot 47^{a_{47}}
- b=2b23b347b47 b = 2^{b_2} \cdot 3^{b_3} \cdot \ldots \cdot 47^{b_{47}}

For each prime k k :
GCD(a,b)=kmin(ak,bk)=kpk \text{GCD}(a, b) = k^{\min(a_k, b_k)} = k^{p_k}
LCM(a,b)=kmax(ak,bk)=k2pk \text{LCM}(a, b) = k^{\max(a_k, b_k)} = k^{2p_k}

Thus, we have:
- min(ak,bk)=pk\min(a_k, b_k) = p_k
- max(ak,bk)=2pk\max(a_k, b_k) = 2p_k

### Step 3: Determine the Number of Solutions for Each Prime

For each prime k k :
- If ak=pk a_k = p_k , then bk b_k can be any integer such that bkpk b_k \geq p_k and bk2pk b_k \leq 2p_k .
- Similarly, if bk=pk b_k = p_k , ak a_k can be any integer such that akpk a_k \geq p_k and ak2pk a_k \leq 2p_k .

This provides two options for each prime k k :
1. (ak,bk)=(pk,2pk) (a_k, b_k) = (p_k, 2p_k)
2. (ak,bk)=(2pk,pk) (a_k, b_k) = (2p_k, p_k)

Since each prime can independently take one of these configurations, we have 22 choices per prime. Given there are 1515 prime numbers from 11 to 5050 (including repeated primes in products like 242^4, 333^3, etc.), the total number of pairs (a,b)(a, b) is:
215=32768 2^{15} = 32768

Thus, the number of pairs (a,b)(a, b) satisfying the given conditions is:
32768 \boxed{32768}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.