Maths Olympiad Prep

Library / /130 of 144

Algebra Difficulty 8.8 Shortlist Find the answer

Call admissible a set AA of integers that has the following property:
If x,yAx,y \in A (possibly x=yx=y) then x2+kxy+y2Ax^2+kxy+y^2 \in A for every integer kk.
Determine all pairs m,nm,n of nonzero integers such that the only admissible set containing both mm and nn is the set of all integers.

[i]

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

Solution

To solve the problem, we aim to determine all pairs (m,n)(m,n) of nonzero integers such that the only admissible set containing both mm and nn is the set of all integers. According to the problem statement, a set AA of integers is admissible if whenever xx and yy are in AA, x2+kxy+y2x^2 + kxy + y^2 is also in AA for every integer kk.

### Step-by-Step Analysis

1. Definition of Admissible Set

Given the definition, for any integers x,yAx, y \in A, the expression x2+kxy+y2x^2 + kxy + y^2 must also be in AA for any integer kk. Notably, choosing specific values for kk yields several important cases:

- When k=0k = 0, this yields x2+y2Ax^2 + y^2 \in A.
- When k=1k = 1, we obtain x2+xy+y2Ax^2 + xy + y^2 \in A.

2. Exploring Consequences

We compute some values to understand the closure of AA under these conditions:

- Starting with elements mm and nn in AA:
- Using the condition k=0k = 0, both m2+n2m^2 + n^2 and n2+m2=2n2n^2 + m^2 = 2n^2 must be in AA.
- Utilizing k=1k = -1, we derive:
m2mn+n2A. m^2 - mn + n^2 \in A.

- If we choose kk such that the expression includes forms like Euclidean algorithms, this could result in generating 1 if mm and nn are coprime:

- Particularly, repeated applications will eventually include elements such as the greatest common divisor of mm and nn.

3. Condition for Admissibility

The minimal condition for a set containing mm and nn to be closed under these operations is gcd(m,n)=1\gcd(m, n) = 1. This means:

- With gcd(m,n)=1\gcd(m,n) = 1, elliptic stepping continually reduces combinations of (m,n)(m, n) down to gcd(m,n)\gcd(m,n).
- Hence, this process can eventually generate any integer, showing AA must be the set of all integers.

4. Conclusion

The problem therefore reduces to determining when any elements mm and nn can generate the full set of integers. This happens precisely when:

gcd(m,n)=1. \gcd(m, n) = 1.

Thus, the set of pairs (m,n)(m, n) such that the only admissible set containing both mm and nn is the set of all integers is exactly those pairs for which gcd(m,n)=1\gcd(m, n) = 1. Consequently, the answer is:

All pairs (m,n) of nonzero integers such that gcd(m,n)=1. \boxed{\text{All pairs } (m, n) \text{ of nonzero integers such that } \gcd(m, n) = 1.}

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.