Let $\mathbb{Z^+}$ and $\mathbb{P}$ denote the set of positive integers and the set of prime numbers, respectively. A set $A$ is called $S-\text{proper}$ where $A, S \subset \mathbb{Z^+}$ if there exists a positive integer $N$ such that for all $a \in A$ and for all $0 \leq b <a$ there exist $s_1, s_2, \ldots, s_n \in S$ satisfying $ b \equiv s_1+s_2+\cdots+s_n \pmod a$ and $1 \leq n \leq N.$ Find a subset $S$ of $\mathbb{Z^+}$ for which $\mathbb{P}$ is $S-\text{proper}$ but $\mathbb{Z^+}$ is not.
Problem
Source: Turkish TST 2012 Problem 9
Tags: modular arithmetic, number theory, prime numbers, number theory proposed
30.03.2012 18:44
Let $\{p_i\}_{i=1}^{\infty},\, p_i < p_{i+1} $, be all prime numbers. Construction of $S=\{s_i\}_{i=1}^\infty$. 1. $s_i=i,\, i:=1,2,\cdots,p_1$. 2. Suppose $s_i, \, i=1,2,\cdots,m,\,m= p_1+p_2+\cdots+p_s$ are chosen. 3. We choose $a_{m+1},a_{m+2},\cdots,a_{m+p_{s+1}}$ consequtiveley, to satisfy the conditions: $a_{m+i} \equiv i \pmod{p_{s+1}}$ and $a_{m+i} \equiv 1 \pmod{p_1p_2\cdots p_s}$ and $a_{m+i}>a_{m+i-1} ,\,i=1,2,\cdots,p_{s+1}$. 4. Go to step 2. Construction of $S$ yields that for every $p\in \mathbb{P}$ and for every resedue modulo $p$, there is an element of $S$ equivalent to that resedue modulo $p$. This means that $\mathbb{P}$ is $S$- proper. Let now show that $\mathbb{Z}^+$ is not $S$- proper. Notice that for each $n\in \mathbb{Z}^+$ and $\forall i>p_1+p_2+\cdots +p_n \,\, \Rightarrow \, s_i \equiv 1 \pmod{p_1p_2\cdots p_n}$ . So, different resedues of elements of $S$ modulo $p_1p_2\cdots p_n$ are at most $p_1+p_2+\cdots+p_n+1$, which is much less than $p_1p_2\cdots p_n$ when $n\to \infty$ and it is not enough $\mathbb{Z}^+$ to be $S$-proper. To get a contradiction let assume $\mathbb{Z}^+$ is $S$- proper and let exists number $N$ as is the definition. Let us choose $m$ big enough so that: (1) $(1+p_1+p_2+\cdots+p_m)^N < (p_1p_2\cdots p_m) $ As said above, the number of different resedues modulo $p_1\cdots p_m$ in $S$ is at most $(1+p_1+p_2+\cdots+p_m)$ and so the number of different sums $s_1+s_2+ \cdots +s_n,\, n \leq N$ is at most $(1+p_1+p_2+\cdots+p_m)^N$. But all resedues modulo $(p_1p_2\cdots p_m) $ are $(p_1p_2\cdots p_m) $ so due to (1) it is not possible all of them to be represented as sum of no more than $N$ elements of $S$. Now, it remains to show why it is possible to choose $m$, so that (1) holds. When $m$ is big enough we can estimate RHS of (1) from below: (2) $ (p_1p_2\cdots p_m) > p_m.\frac{p_m}{2}.\frac{p_m}{4}\cdots \frac{p_m}{2^{2N}} > \frac{p_m^{2N+1}}{C(N)} >$ $ > \frac{p_m}{C(N)} m^N.p_m^N >\frac{p_m}{C(N)}(1+p_1+\cdots+p_m)^N $ where $C(N)$ is a constant depending only on $N$. Pluging in (2) big enough $p_m$ will ensure (1).
06.06.2012 00:59
The set $ S=\{k.5^{k-1}:k\in\mathbb{Z^{+}}\} $ works.
16.06.2012 08:48
Could You explain please why ?
16.06.2012 12:47
($ S=\{k.5^{k-1}:k\in\mathbb{Z^{+}}\} $) 1. $ \mathbb{P} $ is $ S-\text{proper} $ $N=5$ is sufficient: For any prime $p\neq 5$, $((p-t+1)p-(p-t+1)+1)5^{((p-t+1)p-(p-t+1)+1)-1}\equiv -(p-t+1)+1\equiv t$ $\pmod p$ for all $t \in \{0,1,...,p-1\}$. For $p=5$, take the minimal element of $S$, $1$. $1,1+1,1+1+1,1+1+1+1,1+1+1+1+1 \equiv 1,2,3,4,0 \pmod 5$ Hence $ \mathbb{P} $ is $ S-\text{proper} $. 2. $\mathbb{Z^+}$ is not $S-\text{proper}$ Assume that there exists a positive integer $N$ satisfying the conditions in the problem. Only first $N$ elements of $S$ are not $0 \pmod {5^{N}}$. Therefore there are $N+1$ different residues of $5^{N}$ in $S$. Let $a_{1},..., a_{N+1}$ be these residues. We will prove that one can obtain at most ${2N\choose N}$ residues with adding some of $a_{i}$ s with at most $N$ terms. Let $a_{i}$ be used $c_{i}$ times in the sum. Then $c_{1}+...+c_{N+1}\leq N$. We can assume $c_{1}+...+c_{N+1}=N$ because $a_{N+1}=0$. There are ${2N\choose N}$ solutions of $c_{1}+...+c_{N+1}=N$. Therefore one can obtain at most ${2N\choose N}$ residues with adding some of $a_{i}$s with at most $N$ terms. $\mathbb{Z^+}$ is not $S-\text{proper}$ because $5^{N}>{2N\choose N}$.
19.08.2019 17:50
Here's a new construction: Take $S$ as a set of all positive integers of the form $\sum_{p \in \mathbb{P}} \{a_{p-1} \times (p-1)! \}$, where $a_{p-1}$ runs through $0,1, 2, \cdots, p-1$. Now we prove that this works: Step 1: The set of primes is S-proper. Take $N=1$; i.e. we claim that all residues $\pmod p$ appear on the set $S$. Note that all integers on the form $k \times (p-1)! + (\text{Something bigger than zero})$, where $k$ runs through $0,1,2, \cdots, p-1$ is a element of $S$; and since $(p-1)! \equiv -1 \pmod p$ by Wilson's, so we had covered all residues $\pmod p$. Step 2: The set of all positive integers is NOT S-proper. Assume that there exist some suitable $N$ which makes $\mathbb{Z}^{+}$ $S$-proper. Take a prime $p$ bigger than $N$, and let $n=(p-1)!$. Since $\mathbb{Z}^{+}$ is $S$-proper, there exists some $s_1, \cdots, s_k \in S$ satisfying $s_1+\cdots+s_k \equiv -1 \pmod n$ and $k \le N$. Let $s_i=\sum_{q \in \mathbb{P}} a_{i, q-1} \times (q-1)!$, then $$\sum s_i \equiv \sum_{1\le i \le k} \sum_{q <p, q: \text{prime}} a_{q-1}(q-1)! \equiv 0 \pmod n,$$and since $$0\le \sum_{1\le i \le k} \sum_{q <p, q: \text{prime}} a_{q-1}(q-1)!\le k \sum_{q<p, q: \text{prime}} (q-1)\times (q-1)! < N \sum_{1\le q \le p-2} \{ q!-(q-1)!\} <N \times (p-2)! <n-1,$$the remainder of $\sum s_i$ when taken $\pmod n$ must be smaller than $n-1$, which leads to a contradiction. So, we're done! Edit: The big motivation behind this was on a attempt to try using factorials; and also noting that for almost all composite $n$: $n | (n-1)!$ holds. This lead to work with only prime factorials.