Let $(p_n)_{n\geq 1}$ be the sequence $2,3,5,7,11,\ldots$ of the prime numbers. Let $m$ be such that $p_m \leq \frac {p-1} {2} < p_{m+1}$. Assume $p_i \nmid p-1$ for some $1\leq i \leq m$. Then the numbers $1+k(p-1)$, for $1\leq k \leq p_i\leq \frac {p-1} {2}$ are pairwise coprime, since if $p_i \mid (1+k(p-1)) - (1+k'(p-1)) = (k-k')(p-1)$ it follows $p_i \mid k-k'$, implying $k=k'$. Since there are $p_i$ of them, one will be divisible by $p_i$, thus not a prime (as $p_i < 1 + (p-1) = p$). Therefore we need $p_i \mid p-1$ for all such $i$, thus $\prod_{i=1}^m p_i \mid p-1$. But by Bertrand's postulate (Chebyshev's theorem) we have $p_{m+1} < 2p_m$, so $\frac {p-1} {2} < p_{m+1} < 2p_m$, hence $p-1 < 4p_m$. This in turn implies $\prod_{i=1}^{m-1} p_i < 4$, hence $m \leq 2$. Therefore $p < 11$. For $p=3$ we have $1+(p-1) = 3$, a prime. For $p=5$ we have $1+(p-1) = 5$, a prime, but $1+2(p-1) = 9$, not a prime. For $p=7$ we have $1+(p-1) = 7$, a prime, $1+2(p-1) = 13$, a prime, and $1+3(p-1) = 19$, a prime. Thus only $p=3$ and $p=7$ satisfy.

For all $k\geq 1$ all are primes greater equal to $p$ .Consider a prime $q\leq \frac{p-1}{2}$ Now by q divides none of $1+(p-1),1+2(p-1),....1+q(p-1)$ so by PHP easily we can see $q|p-1$ So obviously there are exactly one or no prime less than $q$ and hence $p<11$ so by checking we get $p=3,7$

Let me make clear what your proof does, subham1729. First, using a generic $q$ for my $p_i$, $1\leq i\leq m$, you condense precisely the first part of my proof. Then, getting that $q\mid p-1$ for all primes $q\leq \frac {p-1} {2}$, you cryptically announce "So obviously there are exactly one or no prime less than $q$". Why $qrs \mid p-1$, with primes $q,r,s \leq \frac {p-1} {2}$, is impossible? How would you tackle that without Bertrand's postulate? Therefore I ask, what is the purpose of your post?

Yes I used Bertrand's postulate but believe me I didn't read your solution before posting... sorry

chaotic_iak wrote: Find all odd prime $p$ such that $1+k(p-1)$ is prime for all integer $k$ where $1 \le k \le \dfrac{p-1}{2}$. $\color{blue}\boxed{\textbf{Answer: 3, 7}}$ $\color{blue}\boxed{\textbf{Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ $\color{red}\boxed{\textbf{If }p\ge 13:}$ $\color{red}\rule{24cm}{0.3pt}$ Let be a odd prime $q\le \frac{p-1}{2}$ Then we have: $$1+(p-1), 1+2(p-1), 1+3(p-1), \ldots , 1+q(p-1) \text{ are prime numbers}$$By Pigeonhole Principle: $$\exists a,b\le \frac{p-1}{2} / 1+a(p-1)\equiv 1+b(p-1)\pmod{q}$$$$\Rightarrow q|(a-b)(p-1), |a-b|<q$$$$\Rightarrow q|p-1$$$$\Rightarrow q|\frac{p-1}{2}...(I)$$By Bertrand's Postulate: $$\exists r \text{ prime }/ 3\le \frac{p-1}{4}<r<\frac{p-1}{2}, r\neq 3$$By $(I):$ $$\Rightarrow r|\frac{p-1}{2} \text{ and }3|\frac{p-1}{2}$$$$\Rightarrow 3r|\frac{p-1}{2}$$$$\Rightarrow \frac{3(p-1)}{2}<3r\le \frac{p-1}{2} (\Rightarrow \Leftarrow)$$$\color{red}\rule{24cm}{0.3pt}$ $\color{red}\boxed{\textbf{If }p\le 12:}$ $\color{red}\rule{24cm}{0.3pt}$ If $p=11: \Rightarrow 1+2(11-1)=21 \text{ is prime} (\Rightarrow \Leftarrow)$ If $p=7: \Rightarrow 1+(7-1)=7, 1+2(7-1)=13, 1+3(7-1)=19 \text{ are primes} \checkmark$ If $p=5: \Rightarrow 1+2(5-1)=0 \text{ is prime} (\Rightarrow \Leftarrow)$ If $p=3: \Rightarrow 1+(3-1)=3 \text{ is prime} \checkmark$ $\color{red}\rule{24cm}{0.3pt}$ $$\Rightarrow \boxed{p=3, 7 \textbf{ are the only solutions}}_\blacksquare$$$\color{blue}\rule{24cm}{0.3pt}$