Maths Olympiad Prep

Library / Czech-Polish-Slovak Match /23 of 30

Czech-Polish-Slovak Match

Number theory Difficulty 6.5 National Olympiad Find the answer

Determine all such pairs pf positive integers (a,b)(a, b) such that a+b+(gcd(a,b))2=lcm(a,b)=2⋅lcm(a−1,b)a + b + (gcd (a, b))^ 2 = lcm (a, b) = 2 \cdot lcm(a -1, b), where lcm(a,b)lcm (a, b) denotes the smallest common multiple, and gcd(a,b)gcd (a, b) denotes the greatest common divisor of numbers a,ba, b.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let us determine all pairs of positive integers (a,b) (a, b) such that:

a+b+(gcd⁡(a,b))2=lcm(a,b)=2⋅lcm(a−1,b) a + b + (\gcd(a, b))^2 = \mathrm{lcm}(a, b) = 2 \cdot \mathrm{lcm}(a-1, b)

where lcm(a,b)\mathrm{lcm}(a, b) is the least common multiple and gcd⁡(a,b)\gcd(a, b) is the greatest common divisor of aa and bb.

### Step 1: Understanding the Equations

The given equations are:

1. a+b+(gcd⁡(a,b))2=lcm(a,b) a + b + (\gcd(a, b))^2 = \mathrm{lcm}(a, b)
2. lcm(a,b)=2⋅lcm(a−1,b) \mathrm{lcm}(a, b) = 2 \cdot \mathrm{lcm}(a-1, b)

Let d=gcd⁡(a,b) d = \gcd(a, b) . Then we can express a a and b b as a=d⋅a1 a = d \cdot a_1 and b=d⋅b1 b = d \cdot b_1 where gcd⁡(a1,b1)=1\gcd(a_1, b_1) = 1.

From the properties of lcm and gcd, we have:

lcm(a,b)=a⋅bgcd⁡(a,b)=d⋅a1⋅d⋅b1d=d⋅a1⋅b1 \mathrm{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)} = \frac{d \cdot a_1 \cdot d \cdot b_1}{d} = d \cdot a_1 \cdot b_1

### Step 2: Analyzing the First Equation

Substituting the expressions for aa, bb, and lcm(a,b)\mathrm{lcm}(a, b) into the first equation:

d⋅a1+d⋅b1+d2=d⋅a1⋅b1 d \cdot a_1 + d \cdot b_1 + d^2 = d \cdot a_1 \cdot b_1

Dividing the entire equation by dd (assuming d≠0d \neq 0):

a1+b1+d=a1⋅b1 a_1 + b_1 + d = a_1 \cdot b_1

This simplifies to:

a1⋅b1−a1−b1=d a_1 \cdot b_1 - a_1 - b_1 = d

### Step 3: Analyzing the Second Equation

Substitute lcm(a−1,b)\mathrm{lcm}(a-1, b) in the second equation:
lcm(a−1,b)=lcm(d⋅a1−1,d⋅b1) \mathrm{lcm}(a-1, b) = \mathrm{lcm}(d \cdot a_1 - 1, d \cdot b_1)

For integers xx and yy, lcm(x,y)=∣x⋅y∣gcd⁡(x,y)\mathrm{lcm}(x, y) = \frac{|x \cdot y|}{\gcd(x, y)}. Thus, the equation becomes:

d⋅a1⋅b1=2⋅lcm(d⋅a1−1,d⋅b1) d \cdot a_1 \cdot b_1 = 2 \cdot \mathrm{lcm}(d \cdot a_1 - 1, d \cdot b_1)

### Step 4: Testing Possible Values

Testing small values for aa and bb that satisfy both equations:

#### Pair (2, 3):

1. gcd(2,3)=1\mathrm{gcd}(2, 3) = 1, lcm(2,3)=6\mathrm{lcm}(2, 3) = 6.
2. Check: 2+3+12=62 + 3 + 1^2 = 6 and 6=2⋅lcm(1,3)=66 = 2 \cdot \mathrm{lcm}(1, 3) = 6.

This pair is valid.

#### Pair (6, 15):

1. gcd(6,15)=3\mathrm{gcd}(6, 15) = 3, lcm(6,15)=30\mathrm{lcm}(6, 15) = 30.
2. Check: 6+15+32=306 + 15 + 3^2 = 30 and 30=2⋅lcm(5,15)=3030 = 2 \cdot \mathrm{lcm}(5, 15) = 30.

This pair is valid.

Thus, the solutions are:
(2,3) and (6,15) \boxed{(2, 3) \text{ and } (6, 15)}

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

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.