Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
What can be said about the following question?
For which prime numbers $p$ there exists another prime number $q(p)$ such that $q(p)$ does not divide $\lambda p +1$ for all integers $\lambda$ ?
For example, $2$ is a prime number not satisfying the above condition. We also know there are infinite prime numbers in the set $\{\lambda p +1 | \lambda \in Z\}$ by Dirichlet's theorem.
Does anybody know a simple answer, or any reference talking about this kind of question?
There does not exist any primes which satisfy the above condition.
The ring of numbers modulo $q$ is a field when $q$ is prime. If $p$ is another prime, then it is a unit in the field, i.e. there exists $p^{-1}$ such that $$p\cdot p^{-1} \equiv 1\ \left(\text{mod}\ q\right)$$ now take $\lambda = (q-1)\cdot p^{-1}$ so that $$\lambda p + 1\equiv (q-1)\cdot p^{-1}\cdot p +1 \equiv q-1 + 1 \equiv 0\ \left(\text{mod}\ q\right)$$ so we can always construct a solution.
Let $p$ be a prime, and let $q$ be a prime other than $p$. Then the congruence $\lambda p+1\equiv 0\pmod{q}$ always has a solution. So there are no primes $p$ with the property you are asking for.
Remark: If you are not familiar with properties of congruences, we prove the result without referring to such properties.
Look at the remainders when the numbers $0\cdot p+1$, $1\cdot p+1$, $2\cdot p+1$, and so on up to $(q-1)\cdot p+1$ are divided by $q$. These remainders are all different. For if $i\cdot p+1$ has the same remainder as $j\cdot p+1$, then $q$ divides $(i\cdot p+1)-(j\cdot p+1)$, so $q$ divides $(i-j)\cdot p$. But since $q\ne p$, it follows that $q$ divides $i-j$. Since $0\le i,j\le q-1$, this forces $i=j$.
Note that we did not need here that $p$ and $q$ are prime. It is enough to assume that $p$ and $q$ have no common divisor greater than $1$ (in other words, that $p$ and $q$ are relatively prime.)
Since the remainders of $0\cdot p+1$, $1\cdot p+1$, $2\cdot p+1$, and so on up to $(q-1)\cdot p+1$ are all different, they must be $0$, $1$, $2$, and so on up to $q-1$, in some order. In particular, there is an $i$ such that the remainder when you divide $i\cdot p+1$ by $q$ is $0$.
Hint $\rm\ \exists\: b\in\mathbb Z\!:\ q\ |\ b p + 1\iff\exists\: a,b\in\mathbb Z\!:\ aq-b p = 1\iff \gcd(q,p) = 1\ $ by Bezout.
