Let $a_1,a_2,a_3,\cdots $ be an infinite sequence of distinct integers. Prove that there are infinitely many primes $p$ that distinct positive integers $i,j,k$ can be found such that $p\mid a_ia_ja_k-1$. Proposed by Mohsen Jamali
Problem
Source: Iranian TST 2018, second exam, day1, problem 3
Tags: number theory
16.04.2018 19:17
any solution ?
17.04.2018 15:21
not a solution, nor do I really know if it helps in solving the problem at all, but it looks like progress so why not post
also
17.04.2018 18:27
$i, j, k$ are distince?
17.04.2018 18:59
nmd27082001 wrote: $i, j, k$ are distince? Yes. Read the problem again.
17.04.2018 20:35
11.07.2018 05:49
Here's a very cheap solution. Assume the contrary. Then the sequences $b_n=a_1a_2a_n-1$ and $c_n=a_1a_3a_n-1$ have only finitely many prime factors, so the sequences $d_n=a_1a_2a_3a_n-a_3$ and $e_n=a_2a_2a_3a_n-a_2$ also have finitely many prime factors. This is a contradiction of Kobayashi's theorem.
26.10.2018 10:14
Let $A={p: p|a_{i}a_{j}a_{k}-1}$, where $p$ is a prime. If $|A|< \infty$, we may assume $A={p_{1}, \cdots, p_{t}}$,and for given $i, j$ , let $$a_{i}a_{j}a_{k}-1=p_{1}^{k_{1}} \cdots p_{t}^{k_{t}},$$and let $M_{K}=: Max{p_{1}^{k_{1}}, \cdots, p_{t}^{k_{t}}}$. We consider $M_k, \cdots, M_{k+t}$, there exist $0 \leq l<n \leq t$, $M_{l}=p^a$, $M_{n}=p^b$, where $p \in {p_{1}, \cdots, p_{t}}$. Without loss the generality, we assume $a<b$, and then $p^{a}|a_{i}a_{j}a_{l}-1$, $p^{a}|a_{i}a_{j}a_{n}-1$, it follows that $p^{a}|a_{l}-a_{n}$, let $i$ is large enough, we get $a_{l}=a_{n}$, a contradiction.
31.01.2019 06:13
Quote: This is a contradiction of Kobayashi's theorem. So what's Kobayashi's theorem? I only find Kobayashi's metric.
02.12.2020 10:09
Suppose for contradiction that only finitely many primes $p_1,\dots, p_r$ divide numbers of the form $a_ia_ja_k-1$. Note that for distinct positive integers $i,j\ge r+2$ and distinct $k_1,k_2\in [r+1]$, \[\gcd(a_ia_ja_{k_1} - 1, a_ia_ja_{k_2}-1) = \gcd(a_ia_ja_{k_1}-1, a_ia_j(a_{k_1} - a_{k_2})) = \gcd(a_ia_ja_{k_1}-1,a_{k_1} - a_{k_2}) \le |a_{k_1} - a_{k_2}|. \tag{1}\]Fix a large $N$ such that $p_t^N > \max_{k_1,k_2 \in [r+1]}|a_{k_1} - a_{k_2}|$ for every $t=1,\dots,r$. Note that for sufficiently large $a_i,a_j$, for any $k$, there exists an index $t\in [r]$ such that $v_{p_t}(a_ia_ja_k - 1) > N$. We fix two such large numbers $a_i$ and $a_j$. Then for any $k\in [r+1]$, there exists an index $t(k)\in [r]$ such that $v_{p_{t(k)}}(a_ia_ja_k - 1) > N$. Because there are $r+1$ choices of $k$, there exist two choices $k_1,k_2$ such that $t(k_1) = t(k_2)$ by pigeonhole. But this violates (1), contradiction.
04.02.2021 20:17
Dadgarnia wrote: Let $a_1,a_2,a_3,\cdots $ be an infinite sequence of distinct integers. Prove that there are infinitely many primes $p$ that distinct positive integers $i,j,k$ can be found such that $p\mid a_ia_ja_k-1$. Proposed by Mohsen Jamali Without loss of generality let us say that $a_2 < a_3$ or else reverse few of the terms of this solution. Let us say that there exist only finitely many primes $p$ that divide $a_ia_ja_k - 1$ for some triple of $(i, j, k) \in \mathbb{N}$. Therefore, only finitely many primes $p$ divide the expression $a_1a_2a_n - 1$ for some $n \in \mathbb{N}$ and therefore finitely many primes $p$ divide the expression $a_1a_2a_3a_n - a_3$ for some $n \in \mathbb{N}$ and due to Kobayashi's Theorem, we must have that infinitely many primes $p$ divide the expression $a_1a_2a_3a_n - a_3 - (a_3-a_2) = a_1a_2a_3a_n - a_2$ for some $n \in \mathbb{N}$ and since $a_2$ is finite integer, we can safely remove $a_2$ from the expression and still have that infinitely many primes $p$ divide the expression $a_1a_3a_n - 1$ for some $n \in \mathbb{N}$ which is the desired conclusion.
19.06.2021 20:20
We will construct two such sequences. Notice that out of the sequences $\{a_1a_2a_3a_i-a_1\},\{a_1a_2a_3a_i-a_2\},\{a_1a_2a_3a_i-a_3\}$, at most one is prime-deficient by Kobayashi's theorem. Simple division finishes from here.
10.09.2021 23:22
I suppose the sole merit of this solution is that it never says the word ``Kobayashi.'' Suppose there are finitely many such primes $p$. Then consider the set of all choices of primes $p_1,p_2,\dots,p_\ell$ and distinct integers $a_1,a_2,\dots$ such that every prime divisor of any $a_ia_ja_k-1$ is contained in $\{p_1,\dots,p_\ell\}$. Pick such a choice with minimal $\ell$. Claim: For any prime $p_t$, we can assume each residue modulo $p_t$ occurs infinitely often or no times at all. Solution: Otherwise, throw away all instances of that residue. $\fbox{}$ Claim: For any prime $p_t$ and a residue $r\pmod{p_t}$, $r^3\equiv 1 \pmod{p_t}$. Solution: Suppose otherwise. Then we can select only $a_i$ congruent to $r$ modulo $p_t$ and use \[p_1,p_2,\dots,p_{t-1},p_{t+1},\dots,p_\ell\]as the set of primes, meaning $\ell$ was not minimal. $\fbox{}$ Claim: For any prime $p_t$, only one residue $r\pmod{p_t}$ need occur for the $a_i$. Solution: Throw away any other residue. If some $a_i$ was $1$, delete it. For an arbitrary prime $p$, define $f_p(a)$ to be $\nu_p(a^3-1)$. Then throw away $a_i$ to ensure that the sequence $f_{p_1}(a_i)$ is monotonically increasing by taking $a_2$ to be the next $a_i$ with $f_{p_1}(a_i)\ge f_{p_1}(a_1)$ and so on. If this algorithm runs out of terms, throw away all $a_i$ taking on the maximal value of $f_{p_1}(a_i)$ and start over. This throws away at most a finite number of terms, so it is ok and ensures that $f_{p_1}(a_1)\le f_{p_1}(a_2)\le \cdots$. Do the same for $p_2,p_3,\dots,p_t$. It is clear that given fixed $a_1$, modulo any $p_i^\ell$ there is exactly one choice of $b$ with $b\equiv a_1\pmod{p_i}$ and $b^3\equiv 1\pmod{p_i^\ell}$. For each $p_i$ such that $f_{p_i}(a_j)$ is eventually constant, pick some $a_j$ with $f_{p_i}(a_j)$ maximal and delete all $a_k$ with $k\le j$. This deletes a finite number of terms, possibly $0$. Now each sequence of $f_{p_i}(a_j)$ is constant or unbounded. For each $p_i$ such that $f_{p_i}(a_j)$ is constant, make sure that the $a_j$ are all the same modulo $p_i^{f_{p_i}(a_1)+1}$ by picking a residue $r$ occurring infinitely many times and making sure all $a_j$ are congruent to it. Now, we present the following claim. Claim: For every prime $p_i$, the sequence of $\nu_{p_i}(a_1a_2a_j-1)$ for $j\ge 3$ is bounded above. Solution: If $p_i$ is such that $f_{p_i}(a_j)$ is a constant sequence, the result is immediate because all $a_1a_2a_j-1$ are divisible by $p_i^{f_{p_i}(a_j)}$ and not by $p_i^{f_{p_i}(a_j)+1}$. So suppose $\nu_{p_i}(a_j)$ is unbounded. Suppose that the sequence $\nu_{p_i}(a_1a_2a_j-1)$ is unbounded as well for contradiction. Let $a_j$ be large and $t=\min(k,\ell)$ where $\ell = f_{p_i}(a_j)$ and $k=\nu_{p_i}(a_1a_2a_j-1)$. Then \[\frac{1}{a_1^3a_2^3}\equiv a_j^3 \equiv 1\pmod{p_i^t}.\]This occurs if and only if $p_i^t\mid a_1^3a_2^3-1$. But $s=\nu_{p_i}(a_1^3a_2^3-1)\ge t$, so $t$ is bounded. Taking larger and larger $a_j$, we see that for some $N$, $j>N$ implies $f_{p_i}(a_j)>t$. Then \[\nu_{p_i}(a_1a_2a_j-1)\le t+\max_{j\le N} \nu_{p_i}(a_1a_2a_j-1).\]This is a finite upper bound. $\fbox{}$ So there are only finitely many possible values of $a_1a_2a_j-1$, which is a contradiction, hence we are done.
18.02.2023 11:42
we can take the sub~(and the number of the primes in ${a_i}$will decrease to $1$
26.04.2024 04:46
Suppose otherwise. WLOG that $a_1, a_2 \ne 1$. Then note that $a_1 a_i a_j - 1$ has finitely many prime divisors as $i,j$ vary and therefore $a_1 a_2 a_i a_j - a_2$ has finitely many prime divisors as $i,j$ vary. By Kobayashi, $a_1 a_2 a_i a_j - a_1$ has infinitely many prime divisors as $i,j$ vary, so $a_2 a_i a_j - 1$ has infinitely many prime divisors as $i,j$ vary, contradiction to the problem statement.
17.08.2024 07:52
Suppose FTSOC that the sequences $b_n=a_{1434}a_{1435}a_n-1$ and $c_n=a_{1434}a_{1436}a_n-1$ have both a finite number of prime factors, then this implies that the sequences $d_n=a_{1436}b_n=a_{1434}a_{1435}a_{1436}a_n-a_{1436}$ and $e_n=a_{1435}c_n=a_{1434}a_{1435}a_{1436}a_n-a_{1435}$ have a finite number of prime factors which contradict Kobayashi's Theorem, therefore one of the sequences above must have infinite prime divisors thus we are done .