# When does a prime $q$ not divide $\lambda p +1$ for all $\lambda$?

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.

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

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