Let $\{a_n\}$ be a sequence of natural numbers such that each prime number greater than $1402$ divides a member of that. Prove that the set of prime divisors of members of sequence $\{b_n\}$ which $b_n=a_1a_2...a_n-1$ , is infinite. Proposed by Navid Safaei
Problem
Source: Iran Team selection test 2024 - P10
Tags: number theory
19.05.2024 19:34
19.05.2024 20:03
Suppose otherwise. Let $S$ be the set of prime numbers that divide infinitely many elements of the sequence $(b_i)$ and $T$ be the set of prime numbers that divide only finitely many elements of this sequence. Clearly $S$ and $T$ are finite sets. Claim: Any prime in $S$ is less than $2024$. Proof: If some prime $p > 2024$ was in $S$, then consider some large $C$ where $p\mid b_C$. If we choose $C$ large enough so that $p$ also divides $a_1a_2\cdots a_C$, we see that $p\mid b_C + 1$, absurd. $\square$ Since $T$ is a finite set and its elements divide only finitely many elements of $(b_i)$, we can let $N$ be the largest positive integer such that a prime in $T$ divides $N$. So for all $n > N$, and all primes $p\in T$, we have $p\nmid b_n$. Hence $b_n$ is only divisible by primes less than $2023$. Now let $P > 2024$ be a prime such that $P\equiv 7\pmod 8$, $P\equiv 1 \pmod q$ for all primes $q < 2024$ with $q \equiv 1\pmod 4$ and $P \equiv -1 \pmod q$ for all primes $q < 2024$ with $q \equiv 3\pmod 4$. Clearly all primes $p < 2024$ are quadratic residues modulo $P$. Choose $M > N$ such that $P\mid a_1 a_2 \ldots a_M$ ($M$ exists since $P > 2024$). We have $b_M = a_1 a_2 \ldots a_M - 1 \equiv -1 \pmod P$. However, all of the prime factors of $b_M$ are quadratic residues modulo $P$, implying that $b_M \equiv -1$ is also a QR modulo $p$. However, this is absurd as $P\equiv 3\pmod 4$.
19.05.2024 20:05
Shayan-TayefehIR wrote: Let $\{a_n\}$ be a sequence of natural numbers such that each prime number greater than $1402$ divides a member of that. Prove that the set of prime divisors of members of sequence $\{b_n\}$ which $b_n=a_1a_2...a_n-1$ , is infinite. For the sake of contradiction suppose that $b_n$ has only finite and let them be $p_1,...,p_k<1402$ ($b_n$ can also have $p>1402$ nut after big $n$ $p$ does not exist).In other words we wotk with $n>N$ Corresponds to the number $b_n$ a binary series of $k$ ones or zero.And let in the $i$ position to have $1$ if $U_{p_i}(b_n)=1(mod2)$ and $0$ otherwise. Then by Php there is a banary sting that cames infinite times let it be $(a_1,....,a_k)$ and also let $x=\prod_{i=1}^{k}p_{i}^{a_{i}}$. So we have that $\prod_{i=1}^{n}a_i-1=xy^2$ for infitive $n$. Then $-x\equiv (xy)^2 (modp)$ for every prime number $p>1402$ contradiction since $-x$ is not a perfect square.
19.05.2024 20:08
Cute problem ! Suppose by contradiction the number of primes is finite. Take those primes to be $p_1,p_2,\dots p_t$ and take $$ a_1a_2\ldots a_n-1=p_1^{\alpha_{1,n}}\cdot p_2^{\alpha_{2,n}}\dots p_t^{\alpha_{t,n}}$$\ Now take a prime $p$ such that : $p \equiv 7 \pmod 8$ And for every prime $q$ among $p_i$ take p such that : 1)If $q\equiv 1 \pmod 4$ take $p \equiv 1 \pmod q$ 2)If $q\equiv 3 \pmod 4$ take $p\equiv r \pmod q$ where $r$ is a quadratic non-residue $\pmod q$ 3) If $q=2$ we don't care. By CRT,dirichlet bla bla this $p$ exists.Take $n$ big enough such that $p\mid a_1a_2\dots a_n$.Now let's see that for every prime $q$ among $p_i$ we have $(\frac{q}{p})=1$.Yeah but if we plug this in the original equation we have $$-1 \equiv p_1^{\alpha_{1,n}}\cdot p_2^{\alpha_{2,n}}\dots p_t^{\alpha_{t,n}} \pmod p $$and taking to legendre symbol $$ (\frac{-1}{p})=(\frac{p_1}{p})^{\alpha_{1,n}}\cdot (\frac{p_2}{p})^{\alpha_{2,n}}\cdot \dots (\frac{p_t}{p})^{\alpha_{t,n}} $$.All the legendre symbols on RHS are $1$ so the product is $1$.But the LHS is $-1$,contradiction ! The problem is solved $\blacksquare$
31.05.2024 10:00
Hi legrndres Let $B$ be the set of divisors of $b_n$. FTSOC suppose $B$ is finite. Let $B'$ be the nonempty subset of $B$ that divides infinitely many elements of $b_n$. Then $B'$ can only contain primes less than $2024$. It remains to find some large prime $p$ such that no number with all divisors in $B'$ is $-1 \pmod{p}$. We take $p$ by Dirichlet such that $p \equiv 3 \pmod{4}$ For any $q \in B', q \equiv 1 \pmod{4}$, $p \equiv 1 \pmod{q}$. For any $q \in B', q \equiv 3 \pmod{4}$, $p \equiv -1 \pmod{q}$. Then $\left(\frac{-1}{p}\right) = -1$, while $\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) \cdot (-1)^{\frac{(p-1)(q-1)}{4}} =1$. The result follows.
02.06.2024 13:15
Dirichlet?
18.07.2024 06:05
Is dirichlet thm allowed here?