Maths Olympiad Prep

Library / /8 of 13

Number theory Difficulty 6.3 National olympiad Find the answer

Find all pairs (a,b)(a,\, b) of positive integers such that 2a12a-1 and 2b+12b+1 are coprime and a+ba+b divides 4ab+1.4ab+1.

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

Solution

We need to find all pairs (a,b)(a, b) of positive integers such that:
1. 2a12a-1 and 2b+12b+1 are coprime,
2. a+ba+b divides 4ab+14ab+1.

### Step 1: Analyze the Conditions

Condition 1:
The integers 2a12a-1 and 2b+12b+1 are coprime, meaning their greatest common divisor (GCD) is 1. Therefore:

gcd(2a1,2b+1)=1 \gcd(2a-1, 2b+1) = 1

This condition ensures that 2a12a-1 and 2b+12b+1 have no common factors other than 1.

Condition 2:
The sum a+ba+b divides 4ab+14ab+1, expressed as:

a+b4ab+1 a+b \mid 4ab+1

This implies that there exists an integer kk such that:

4ab+1=k(a+b) 4ab + 1 = k(a+b)

Rearranging gives:

4ab+1=ka+kb4ab+1kakb=0(4ak)b=ka1 4ab + 1 = ka + kb \quad \Rightarrow \quad 4ab + 1 - ka - kb = 0 \quad \Rightarrow \quad (4a - k)b = ka - 1

From this expression, find conditions that will satisfy both divisibility and coprimacy.

### Step 2: Find Possible Solutions

Let's assume b=a+1b = a + 1, and we will verify whether this satisfies both conditions:

1. Coprime Check:
- 2a12a-1 becomes 2a12a-1.
- 2b+12b+1 becomes 2(a+1)+1=2a+32(a+1)+1 = 2a + 3.

We check for coprimacy:

gcd(2a1,2a+3)=gcd(2a1,4)=1 \gcd(2a-1, 2a+3) = \gcd(2a-1, 4) = 1

Thus, they are coprime when the GCD is 1.

2. Divisibility Check:
- a+b=a+(a+1)=2a+1a + b = a + (a + 1) = 2a + 1
- This divisibility condition becomes:

2a+14ab+1 2a + 1 \mid 4ab + 1

Substituting b=a+1b = a + 1 gives:

4a(a+1)+1=4a2+4a+1 4a(a+1) + 1 = 4a^2 + 4a + 1

Check:

4a2+4a+1÷(2a+1)=2a+1 4a^2 + 4a + 1 \div (2a + 1) = 2a + 1

The quotient is an integer, so this condition satisfies the divisibility requirement under the assumption.

Therefore, the pair (a,a+1)(a, a+1) satisfies all conditions.

### Conclusion

From the steps above, the only pairs (a,b)(a, b) that satisfy the given conditions are:

(a,a+1) \boxed{(a, a+1)}

This solution set meets both the coprimacy and divisibility requirements.

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.