Let $n$ and $M$ be positive integers such that $M>n^{n-1}$. Prove that there are $n$ distinct primes $p_1,p_2,p_3 \cdots ,p_n$ such that $p_j$ divides $M + j$ for all $1 \le j \le n$.
Problem
Source:
Tags:
Kayak
20.01.2019 15:35
Hint: USAMO 2014/6 If M+i's have prime divisor exceeding n then we can ignore it. Crate a bipartite graph with the M+i's with all prime factor < n on one side and primes < n on a other side and uae some v_p bounding to show matching condition is met.
fattypiggy123
20.01.2019 15:50
Tuymaada 2004.
Supercali
20.01.2019 19:56
If $M+i$ has a prime factor $q > n$ choose $p_i = q$. Else all prime factors of $M+i$ are less than $n$. Since there are at most $n-1$ primes less than $n$ there must exist a prime power $r^k >n$ which divides $M+i$. Then choose $p_i = r$.
This solution works even if $M > n^ {\pi(n)}$
This problem reminded me of a certain IMO problem.
zephyr7723
20.01.2019 21:03
Supercali wrote:
If $M+i$ has a prime factor $q > n$ choose $p_i = q$. Else all prime factors of $M+i$ are less than $n$. Since there are at most $n-1$ primes less than $n$ there must exist a prime power $r^k >n$ which divides $M+i$. Then choose $p_i = r$.
This solution works even if $M > n^ {\pi(n)}$
This problem reminded me of a certain IMO problem. My solution was also based on this solution somewhat, though i did a blunder while writing the solution.
sa2001
21.01.2019 08:13
Divide each $M + i$ by $gcd(M+i, (n-1)!)$.
Note that this gives us a list of $n$ pairwise coprime naturals, each greater than $1$.
So the required selection of primes exists, and we're done.
e_plus_pi
21.01.2019 09:27
$ $
Severus
25.01.2019 11:06
sa2001 wrote:
Divide each $M + i$ by $gcd(M+i, (n-1)!)$.
Note that this gives us a list of $n$ pairwise coprime naturals, each greater than $1$.
So the required selection of primes exists, and we're done.
I don't know why this solution got unnoticed but I find this one quite a cool method. It reduces the bound on $M$ to $M\geq (n-1)!$.
paragdey01
08.02.2019 10:46
An example for a case Let $M+j=n^(n–1) +t +1$ And let $p_j =6k+1$,$k>0$ be a prime Set $n=6k+1$ $M+j=(6k+1)^6k +(t +1)$ For $6k+1|(6k+1)^6k +(t+1)$ We must have $6k+1|(t+1)$ $t+1=(6k+1)s$ Now this have some solutions many set $t=2^f –3$ and $s=2m$ If $(k, m) =(1,1)$ and $f=4$ $2^f –2 =14$ And $6k+1*2m=7*2=14$
AlastorMoody
08.01.2020 19:20
Almost similar to a problem from Brazil CSMO TST
ftheftics
25.03.2020 08:33
If one assume the there is a prime $p_i\mid M+k,M+r$ then ,$p_i \mid |k-r| $ which Implies , $M<\min {M+k,M+r}<(p_i^{\min v_p(M+k),v_p(M+r)} |k-r|)^{n-1} <n^{n-1}$ . This contradiction may prove this case sa2001 wrote:
Divide each $M + i$ by $gcd(M+i, (n-1)!)$.
Note that this gives us a list of $n$ pairwise coprime naturals, each greater than $1$.
So the required selection of primes exists, and we're done.
It is the most beautiful way to do .
ftheftics
26.03.2020 06:07
Kayak wrote: Hint: USAMO 2014/6 If M+i's have prime divisor exceeding n then we can ignore it. Crate a bipartite graph with the M+i's with all prime factor < n on one side and primes < n on a other side and uae some v_p bounding to show matching condition is met. Can u give more hint ... How to deal with that bipartite graph
Krish230905
24.12.2020 19:41
If $M+j$ has atleast $n$ prime divisors, we take the one which is distinct from all the other ones. If it has less than $n$ prime factors, as $M+j>M>n^{n-1}$ ,we have a prime $p$ as its factor, such that $p>n$. As all $M+j$ such that $0\le j\le n$ lie on an interval of $n$ then we have that this $p$ doesn't divide any other number.
Maths_1729
08.02.2021 20:56
Redacted