Let $S$ be an infinite set of positive integers and define: $T=\{ x+y|x,y \in S , x \neq y \} $ Suppose that there are only finite primes $p$ so that: 1.$p \equiv 1 \pmod 4$ 2.There exists a positive integer $s$ so that $p|s,s \in T$. Prove that there are infinity many primes that divide at least one term of $S$.
Problem
Source: Iranian third round midterm number theory exam problem 3
Tags: number theory, kobayashi
04.08.2019 22:32
Generalization:If at most $k$ primes divide at least one term of $S$ and at most $t$ primes congurent to $1$ mod $4$ dividing at least one term of $T$ then $S$ can't have at most $2^{2k+t}$ members.Unless I am missing something obvious the proof of the generalization is much harder.
28.10.2019 04:02
I don't know whether it is right because I have not use that condition. If $\{p : p \mid x, x\in T, p \text{ is a prime}\}=\{p_1, p_2, \cdots, p_t\}$, we select $y_1, y_2, \cdots, y_n \in S$, $n=t+1$, $y_i \neq y_j$. We fix large enough $x \in S$, $\sqrt[t]{x}>\max\{y_1,y_2,\cdots,y_t\}$, $$x+y_j=p_1^{\alpha_{1,j}^{(x)}}p_2^{\alpha_{2,j}^{(x)}} \cdots p_t^{\alpha_{t,j}^{(x)}}, j=1,2,\cdots,n.$$Consider $M_j=\max\limits_{1 \leq i\leq t} \{p_i^{\alpha_{i,j}^{(x)}} \}$, $i=1,2,\cdots,n$. Notice $n=t+1$, Pigeonhole principle tells us that there exist $i \neq j \in \{1,2,\cdots,t+1\}$, such that $M_i=p^\alpha$, $M_j=p^\beta$, $p \in \{p_1, p_2, \cdots, p_t\}$, we assume $\alpha \leq \beta$, then $p^\alpha \mid x+y_i$, $p^\alpha \mid x+y_j$, we can get $p^\alpha \mid y_i-y_j$, but $p^\alpha \geq \sqrt[t]{x+y_i}>\sqrt[t]{x}>|y_i-y_j| > 0$, a contradiction.
28.10.2019 09:10
Sorry, I read the wrong question, we need prove $S$ has infinite prime factors.
29.10.2019 06:34
I'm back, I will correct my joke of yesterday. Please help me to check. First we need a Lemma which I have written in 3 floor: Lemma: Let $X \subset \mathbb{Z}_+$, $|X|=+\infty$, then $\left|\{p : p \text{ is a prime}, p \mid x+y, x,y\in X, x\neq y\}\right|=+\infty$. Proof of Lemma: If $\{p : p \mid x+y, x,y\in X, x\neq y, p \text{ is a prime}\}=\{p_1, p_2, \cdots, p_t\}$, we select $y_1, y_2, \cdots, y_n \in X$, $n=t+1$, $y_i \neq y_j$. We fix large enough $x \in X$, $\sqrt[t]{x}>\max\{y_1,y_2,\cdots,y_t\}$, $$x+y_j=p_1^{\alpha_{1,j}^{(x)}}p_2^{\alpha_{2,j}^{(x)}} \cdots p_t^{\alpha_{t,j}^{(x)}}, j=1,2,\cdots,n.$$Consider $M_j=\max\limits_{1 \leq i\leq t} \{p_i^{\alpha_{i,j}^{(x)}} \}$, $i=1,2,\cdots,n$. Notice $n=t+1$, Pigeonhole principle tells us that there exist $i \neq j \in \{1,2,\cdots,t+1\}$, such that $M_i=p^\alpha$, $M_j=p^\beta$, $p \in \{p_1, p_2, \cdots, p_t\}$, we assume $\alpha \leq \beta$, then $p^\alpha \mid x+y_i$, $p^\alpha \mid x+y_j$, we can get $p^\alpha \mid y_i-y_j$, but $p^\alpha \geq \sqrt[t]{x+y_i}>\sqrt[t]{x}>|y_i-y_j| > 0$, a contradiction. Now back: If $A=\{p : p \mid x, x\in S, p \text{ is a prime}\}$ is finite, assume $B=\{p: p\mid x, x\in T, p \equiv 1(mod 4), p \text{ is a prime}\}$, for any $x \in S$, $$x=p_1^{\alpha_{1}^{(x)}}p_2^{\alpha_{2}^{(x)}} \cdots p_t^{\alpha_{t}^{(x)}},$$consider vector set $$V=\{(\alpha_{1}^{(x)}, \alpha_{2}^{(x)}, \cdots, \alpha_{t}^{(x)}): x\in S\},$$there exist $V_1 \subset V$, $|V_1|=+\infty$, such that for any $$(\alpha_{1}^{(x)}, \alpha_{2}^{(x)}, \cdots, \alpha_{t}^{(x)}), (\alpha_{1}^{(y)}, \alpha_{2}^{(y)}, \cdots, \alpha_{t}^{(y)}) \in V_1, $$$$(\alpha_{1}^{(x)}, \alpha_{2}^{(x)}, \cdots, \alpha_{t}^{(x)}) \equiv (\alpha_{1}^{(y)}, \alpha_{2}^{(y)}, \cdots, \alpha_{t}^{(y)}) (mod 2).$$Consider $$S_1=\{p_1^{c_1}p_2^{c_2}\cdots p_t^{c_t}: (c_1,c_2,\cdots,c_t)\in V_1\},$$$|S_1|=+\infty$, $$x+y=p_1^{\alpha_{1}^{(x)}}p_2^{\alpha_{2}^{(x)}} \cdots p_t^{\alpha_{t}^{(x)}}+p_1^{\alpha_{1}^{(y)}}p_2^{\alpha_{2}^{(y)}} \cdots p_t^{\alpha_{t}^{(y)}},$$where $x,y \in S_1$, notice there exist $\alpha_{k}^{(x)} \neq \alpha_{k}^{(y)}$, then by the Lemma we can find a prime $p$ which is large enough, such that $p \notin A \cup B$, $p \mid x+y$, and $\left( \frac{-1}{p}\right)=1$, then $p \equiv 1(mod 4)$, but $p \notin B$, a contradiction.
06.12.2019 15:30
I have improved my expression, and this is Kobayashi Th: https://artofproblemsolving.com/community/c6h362152
04.04.2021 13:42
Let $\aleph_{(r,k)} \left( A \right)$, be the number of primes $p$, such that there exists $a \in A$ such that $p \mid a$ and $p \equiv r \pmod{k}$. By the conditions given we must have that $\aleph_{(1,4)} \left( T \right)$ exists. Now fix $y \in S$ define set $A$ to be $A=\{ t-y \mid t\in T \}$, then notice that $A \subset S$. By Kobayashi, we must have that $\aleph\left( A \right)$ doesn't exist, where $\aleph\left( A\right)$ is the number of such primes $p$ such that there exists $a \in A$, such that $p \mid a$. Since $A \subset S$, this implies that $\aleph(S)$ also doesn't exist, which proves the statement.
30.08.2022 20:49
Lemma:Let $S \subset \mathbb{N}$ be an infinite set and $T_S=\{ x+y|x,y \in S , x \neq y \} $ , then there exist infinitely many prime numbers $p$ , such that for a $t \in T_S$ we have $p|t$. Proof:by induction on $k$ , we'll show that if primes $p_1 , ... , p_k$ are distinct factors from members of the set $T_S$ , then there exist a prime $p_{k+1}$ distinct from these $k$ numbers such that for a $t \in T_S$ , we have $p_{k+1}|t$. We assign $k-$tuple $(\alpha_{(i,1)},...,\alpha_{(i,k)})$ to each member $s_i \in S$ such that $\alpha_{(i,j)}=v_{p_j}(s_i)$. Now if there exist an odd prime $p_j$ such that the value of $\alpha_{(i,j)}$ are equal for infinitely many $i \in \mathbb{N}$ , then consider infinite set $S' \subset S$ such that for each member $s$ of that , we have $v_{p_j}(s)=\alpha_{(i,j)}$. So if for each $s \in S'$ , we define $s=p_{j}^{\alpha_{(i,j)}}s'$ , then between numbers $s_i'$ by pigeonhole principle , there exist infinitely many numbers which are equal and non-zero module $p_j$ and pairwise sum of these numbers have at most $k-1$ prime factors ( not $p_j$ ) between $p_1 , ... , p_k$. So by induction case for $k-1$ , there exist a prime factor distinct from these $k$ numbers for these chosen numbers from $T_S$. So suppose that for each prime $p_j$ and $i \in \mathbb{N}$ , there exist only finitely many numbers $s$ in $S$ such that $v_{p_j}(s)=\alpha_{(i,j)}$.Then one can consider infinite set $S' \subset S$ such that for each members $s_i , s_j$ of that , there doesn't exist $r \le k$ such that $\alpha_{(i,r)}=\alpha_{(j,r)}$. As the result for each arbitrary members of $S'$ we can get : $$v_{p_r}(s_i+s_j)=\min(\alpha_{(i,r)} , \alpha_{(j,r)})$$then obviously by inequalities , $s_i+s_j$ has a prime factor distinct from $p_1 , ... , p_k$ and lemma is proved for this case too. (Note that if one power of prime $2$ repeats infinitely many times between members of $S$ , then by taking odd factors of these numbers ( were are equal module $4$ ) , the rest of the proof for this case is similar to above one. ) Now if members of the set $S$ has finitely many prime factors $p_1 , ... , p_k$ , then again by induction on $k$ we'll show that members of $T$ has infinitely many prime factors in form $4k'+1$. Similar to lemma above , define $k-$tuple $(\alpha_{(i,1)},...,\alpha_{(i,k)})$ and if there exist a prime $p_j$ that values of $\alpha_{(i,j)}$ are equal for infinitely many $i$ , then by considering this infinite numbers $s \in S$ and $s=p_{j}^{\alpha{(i,j)}}s'$ , the set of values $s'$ has $k-1$ prime factors distinct from $p_j$ and by our induction case , their pairwise sum produce infinitely many prime factors in form $4k'+1$. So assume otherwise , then there exist an infinite set $S'=\{s_1 , s_2 , ... \} \subset S$ such that for each $i>j$ and $r \le k$ , we have $\alpha_{(i,r)}>\alpha_{(j,r)}$. Now since the parity of values $(\alpha_{(i,1)},...,\alpha_{(i,k)})$ has $2^k$ different cases , by pigeonhole principle one can choose infinitely many members of $S'$ such that for each chosen $s_i , s_j$ and $r$ , $\alpha_{(i,r)}$ and $\alpha_{(j,r)}$ have same parity. As the result , for each chosen $i>j$ we have : $$s_i+s_j=s_j(\prod p_{r}^{\alpha_{(i,r)}-\alpha_{(j,r)}}+1)$$Now since $\alpha_{(i,r)}-\alpha_{(j,r)}$ is even and $\left( \frac{-1}{p}\right)=1$ just for $p \equiv 1 \pmod 4$ , so all prime factors of values $s_i+s_j$ from chosen numbers of $S'$ except $p_1 , ... , p_k$ are in the form $4k'+1$ which by lemma , the number of them is infinite. So we're done.