Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this 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.

share|cite|improve this answer

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

share|cite|improve this answer
Explicitly, for prime $q\neq p$ you can set $\lambda = -p^{q-2}$. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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