Maths Olympiad Prep

Library / /20 of 27

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)=2lcm(a1,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. Spacing and $ signs are ignored.

Solution

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

a+b+(gcd(a,b))2=lcm(a,b)=2lcm(a1,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)=2lcm(a1,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=da1 a = d \cdot a_1 and b=db1 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)=abgcd(a,b)=da1db1d=da1b1 \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:

da1+db1+d2=da1b1 d \cdot a_1 + d \cdot b_1 + d^2 = d \cdot a_1 \cdot b_1

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

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

This simplifies to:

a1b1a1b1=d a_1 \cdot b_1 - a_1 - b_1 = d

### Step 3: Analyzing the Second Equation

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

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

da1b1=2lcm(da11,db1) 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=2lcm(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=2lcm(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,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.