# Find all the prime numbers $p,q$ that satisfy both $p\mid q+6$ and $q\mid p+7$.

Some observations: $$\begin{cases}\begin{cases}q+6=pk\Rightarrow q=pk-6\\ p+7=ql\Rightarrow p+7=(pk-6)l\Rightarrow p-pkl=-6l-7\Rightarrow p(kl-1)=6l+7\end{cases} \begin{cases}p+7=ql\Rightarrow p=ql-7\\ q+6=pk\Rightarrow q+6=(ql-7)k\Rightarrow q-qlk=-7k-6\Rightarrow q(kl-1)=7k+6\end{cases}\end{cases}\Rightarrow \begin{cases}p\mid 6l+7\\ q\mid 7k+6\end{cases}$$

So $p$ gives a remainder $1$ when divided by $6$ and $q$ gives a remainer $6$ when divided by $7$. In other words:$$\begin{cases}p\equiv 1\pmod 6\\q\equiv 6\pmod 7\end{cases}$$ All this is probably not useful at all. I've simply written a few of my observations. So could anyone help me out? Thanks.

• How about $p\le q+6$ and $q\le p+7$, which rearranges to $q-7\le p\le q+6$. Further, unless they're both equalities, either $p\le \frac{q+6}{2}$ or $q\le \frac{p+7}{2}$. Dec 23, 2013 at 1:27
• @vadim123 how did you get the last bounds? Dec 23, 2013 at 1:35
• If $a|b$ then there is some integer $c$ such that $ac=b$. Assume $a,b,c>0$. If $c\neq 1$, then $c\ge 2$. Dec 23, 2013 at 1:37

Note that the size of $p$ and $q$ is limited by the two conditions: $$p \mid q+6 \text{ and } q \mid p+7 \Rightarrow pq \mid (6p+7q+42) \Rightarrow pq \leq (6p+7q+42)$$ Now you can show that $p,q\geq 16$ is a contradiction to the above inequality. So either $p \leq 13$ or $q \leq 13$. But as we have the two divisibility conditions, this also limits the other number (to $19$ in this example). So you find all solutions by testing numbers smaller than these bounds.
Hint: If you want to cross-check your result: I found exactly one tuple $(p,q)$ satisfying the properties.