Maths Olympiad Prep

Library / /29 of 33

Number theory Difficulty 8.6 Shortlist Prove it Turkey

Let Z+Z^+ denote the set of all positive integers and PP denote the set of all prime numbers. For subsets AA and SS of Z+Z^+, AA is called SS-proper if there exists a positive integer NN such that for all aAa \in A and integer bb with 0b<a0 \le b < a there exist not necessarily distinct elements s1,s2,,sns_1, s_2, \dots, s_n of SS satisfying the conditions bs1+s2++sn(moda)b \equiv s_1 + s_2 + \dots + s_n \pmod a and 1nN1 \le n \le N. Find a subset SS of Z+Z^+ for which PP is SS-proper but Z+Z^+ is not.

Solution

We will show that the set S={k5k1:kZ+}S = \{k \cdot 5^{k-1} : k \in \mathbb{Z}^+\} is an appropriate example.

We first prove that P\mathbb{P} is SS-proper for N=4N = 4. Let p5p \neq 5 be prime and 0n<p0 \le n < p. Then by Chinese remainder theorem there exists a positive integer kk satisfying the conditions kn(modp)k \equiv n \pmod{p} and k1(modp1)k \equiv 1 \pmod{p-1}. Therefore, by Fermat's theorem we obtain that k5k1n(modp)k \cdot 5^{k-1} \equiv n \pmod{p}. For p=5p = 5; as 1,10S1, 10 \in S, N=4N = 4 works.

Now suppose that Z+\mathbb{Z}^+ is SS-proper. Then there exists a positive integer NN satisfying the given conditions. Therefore we can get any residue in (mod 5N)(\text{mod } 5^N) as sum of at most NN elements of SS. Since k5k10(mod5N)k \cdot 5^{k-1} \equiv 0 \pmod{5^N} for all k>Nk > N, we have that for each integer 0n<5N0 \le n < 5^N, there exist non-negative integers x1,x2,,xNx_1, x_2, \dots, x_N such that
x11+x225++xii5i1++xNN5N1n(mod5N) x_1 \cdot 1 + x_2 \cdot 2 \cdot 5 + \dots + x_i \cdot i \cdot 5^{i-1} + \dots + x_N \cdot N \cdot 5^{N-1} \equiv n \pmod{5^N}
and x1+x2++xNNx_1 + x_2 + \dots + x_N \le N. Observe that for each nn, we get a different NN-tuple. On the other hand, the number of NN-tuples of non-negative integers satisfying x1+x2++xNNx_1 + x_2 + \dots + x_N \le N is (2NN)<5N\binom{2N}{N} < 5^N and hence we get a contradiction.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.