Let $(a_i)_{i\in \mathbb{N}}$ a sequence of positive integers, such that for any finite, non-empty subset $S$ of $\mathbb{N}$, the integer$$\Pi_{k\in S} a_k -1$$is prime. Prove that the number of $a_i$'s with $i\in \mathbb{N}$ such that $a_i$ has less than $m$ distincts prime factors is finite.
Problem
Source: The francophone mathematical olympiads P4
Tags: number theory, Francophone
neyft
27.06.2020 22:31
Can $(a_i)$ be infinite in the first place?
Gomes17
28.06.2020 01:29
Main Claim. Every prime number $p$ divides all but finitely many elements in the sequence. Proof. First notice that all elements in the sequence are greater than $2$ (Take $S = {a_i}$ for instance). If we have any number $x$ not divisible by $p$ appearing $2p-2$ times (or more) in the sequence, we immediately see that $x^{2p-2}-1$ is not prime, as $x^{2p-2}-1 >p$ and divisible by $p$. Therefore, if there are infinitely many numbers not divisible by $p$ in the sequence, we may take $p$ distinct of them $b_1,b_2,...,b_p$ with every single one of them greater than $p+1$. By looking at the partial products $b_1,b_1b_2,...,b_1...b_p$, we see by PHP that there must be two of them congruent mod $p$. Hence, we end up with $b_ib_{i+1}...b_j -1$ divisible by $p$ and greater than $p$. And now, for any $p$ of the $m$ first prime numbers, take an $N_p$ such that if $i \ge N_p$, then $p|a_i$. Then all numbers in the sequence with index greater than $\max(N_p)_{p \text{ in the first } m \text{ prime numbers}}$ have at least $m$ distinct prime factors.
test20
28.06.2020 18:56
Could you please provide more information on the francophone mathematical olympiad? Is there a webpage with problem collections? What are the participating countries? How many participants are there? What is the level of difficulty?
anyone__42
28.06.2020 23:40
test20 wrote: Could you please provide more information on the francophone mathematical olympiad? Is there a webpage with problem collections? What are the participating countries? How many participants are there? What is the level of difficulty? this is the first version of that competition, the countries that can participate are francophone countries (I think France, Belgium, Luxembourg, Switzerland, Morocco and ivory coast are the ones that participated this year) For the difficiulty you can check the problems I posted, P4 and P3 were on the easy side and P1 was a medium problem, I might translate the combi problem and post it later. for your first question, I don't think they have a website at the moment but if they ever make one to share results I will send it yo you