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$.

  • $\begingroup$ Explicitly, for prime $q\neq p$ you can set $\lambda = -p^{q-2}$. $\endgroup$ – Thomas Andrews Apr 11 '12 at 20:19

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.