Maths Olympiad Prep

Library / /1 of 21

Number theory Difficulty 6.4 National olympiad Find the answer

Find all positive integers, such that there exist positive integers a,b,ca, b, c, satisfying gcd(a,b,c)=1\gcd(a, b, c)=1 and n=gcd(ab+c,acb)=a+b+cn=\gcd(ab+c, ac-b)=a+b+c.

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

Solution

To solve the problem, we must find all positive integers n n such that there exist positive integers a,b,c a, b, c with gcd(a,b,c)=1 \gcd(a, b, c) = 1 and fulfilling the equation:

n=gcd(ab+c,acb)=a+b+c. n = \gcd(ab+c, ac-b) = a+b+c.

### Step-by-Step Analysis

1. Equation Setup:
- Given n=gcd(ab+c,acb)=a+b+c n = \gcd(ab+c, ac-b) = a + b + c .

2. Understanding the Conditions:
- We need to ensure that gcd(a,b,c)=1 \gcd(a, b, c) = 1 , meaning a,b,c a, b, c are coprime.
- The expression n=a+b+c n = a + b + c implies we are looking for n n as a sum of positive integers related to the gcd of specific polynomial forms.

3. Apply GCD Properties:
- From number theory, for any two numbers x x and y y , we have:
gcd(x,y)xy. \gcd(x, y) \mid x - y.
- This implies:
gcd(ab+c,acb)(ab+c)(acb)=ab+cac+b=b(a+1)+cac. \gcd(ab+c, ac-b) \mid (ab+c) - (ac-b) = ab + c - ac + b = b(a+1) + c - ac.

4. **Finding Relation with (mod4) \pmod{4} **:
- Consider the expressions modulo 4, since n n should have prime factors that are 1(mod4) 1 \pmod{4} . This implies that for each chosen a,b,c a, b, c :
ab+ca+b+c0(mod4) ab+c \equiv a+b+c \equiv 0 \pmod{4}
acba+b+c0(mod4) ac-b \equiv a+b+c \equiv 0 \pmod{4}

5. **Concluding the Structure of n n **:
- One can observe that the gcd and sum relationships imply that every prime factor of n n contributes specifically by forming structures like 1(mod4) 1 \pmod{4} which satisfies both gcd and addition.
- Therefore, with the gcd condition, the sum a+b+c=n a+b+c = n and factor parity, it is necessary that n n accommodates the balancing structure enabled by primes 1(mod4) 1 \pmod{4} .

Thus, the full set of possible positive integers n n can be represented as:

All positive integers n with prime factors 1(mod4). \boxed{\text{All positive integers } n \text{ with prime factors } 1 \pmod{4}.}

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.