Maths Olympiad Prep

Library / /75 of 97

Number theory Difficulty 8.3 Shortlist Find the answer

Does there exist a finite set AA of positive integers of at least two elements and an infinite set BB of positive integers, such that any two distinct elements in A+BA+B are coprime, and for any coprime positive integers m,nm,n, there exists an element xx in A+BA+B satisfying xn(modm)x\equiv n \pmod m ?

Here A+B={a+baA,bB}A+B=\{a+b|a\in A, b\in B\}.

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

Solution

To determine whether there exists a finite set A A of positive integers of at least two elements and an infinite set B B of positive integers such that any two distinct elements in A+B A+B are coprime, and for any coprime positive integers m,n m, n , there exists an element x x in A+B A+B satisfying xn(modm) x \equiv n \pmod{m} , we proceed as follows:

### Proof by Contradiction

Assume, for the sake of contradiction, that such sets A A and B B exist, with A={a1,a2,,ak} A = \{a_1, a_2, \ldots, a_k\} .

#### Lemma 1
If (A,B) (A, B) satisfy the conditions of the problem with A=k |A| = k , then there exist infinitely many bB b \in B such that the number ai+b a_i + b has at least k k distinct prime divisors.

Proof of Lemma 1:
Let m1,m2,,mk m_1, m_2, \ldots, m_k be pairwise coprime numbers with at least k k prime divisors each. Let m=m1m2mk m = m_1 m_2 \ldots m_k , and let n n be chosen such that naiai+1(modmi) n \equiv a_i - a_{i+1} \pmod{m_i} for all i i (indices are modulo k k ). Since (A,B) (A, B) satisfy the conditions of the problem, there exists ai,b a_i, b such that
ai+bn(modm). a_i + b \equiv n \pmod{m}.
Therefore,
ai+baiai+1(modmi). a_i + b \equiv a_i - a_{i+1} \pmod{m_i}.
Now,
ai+1+b0(modmi), a_{i+1} + b \equiv 0 \pmod{m_i},
which proves the statement.

#### Main Proof
Let b b be an arbitrarily large number satisfying the condition of Lemma 1. Without loss of generality (after suitable relabeling), let the respective ai a_i be a1 a_1 .

Let p1,p2,,pk p_1, p_2, \ldots, p_k be distinct primes dividing b+a1 b + a_1 . Choose m=p1p2pk m = p_1 p_2 \ldots p_k , and n n such that
naiai+1(modpi) n \equiv a_i - a_{i+1} \pmod{p_i}
for all 1ik 1 \le i \le k , where indices are considered modulo k k . By the Chinese Remainder Theorem, n n corresponds to some residue modulo m m . By assuming that pi p_i are large enough (that is, larger than ai+1ai |a_{i+1} - a_i| for all i i ), we can guarantee (m,n)=1 (m, n) = 1 . To get pi p_i large, just increase b b if necessary: as the elements of A+B A+B are coprime, only finitely many bB b' \in B may be such that b+ai b' + a_i has a "small" prime divisor dividing ai+1ai |a_{i+1} - a_i| for some i i .

Now, assume there exists some cB c \in B such that x=ai+c x = a_i + c (1in 1 \le i \le n ) satisfies xn(modm) x \equiv n \pmod{m} . This, in particular, implies
ai+caiai+1(modpi). a_i + c \equiv a_i - a_{i+1} \pmod{p_i}.
This implies
ai+1+c0(modpi), a_{i+1} + c \equiv 0 \pmod{p_i},
with ai+1+cA+B a_{i+1} + c \in A + B . Since the elements of A+B A+B are pairwise coprime, this implies c=b c = b , with the b b described as above. Additionally,
ai+1+b0(modp1), a_{i+1} + b \equiv 0 \pmod{p_1},
and
a1+b0(modp1) a_1 + b \equiv 0 \pmod{p_1}
by definition, so ai+1=a1 a_{i+1} = a_1 , and therefore i0(modk) i \equiv 0 \pmod{k} . That is,
a1+bn(modm). a_1 + b \equiv n \pmod{m}.
Now,
a1+bna1a2(modp1), a_1 + b \equiv n \equiv a_1 - a_2 \pmod{p_1},
and also
a1+b0(modp1). a_1 + b \equiv 0 \pmod{p_1}.
This means that a1a2(modp1) a_1 \equiv a_2 \pmod{p_1} , which cannot happen for big enough p1 p_1 . As explained before, we can force the pi p_i to be as large as we want. This, finally, is a contradiction.

Therefore, the answer is: \boxed{\text{No}}.

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.