Find all primes $p,q$ such that $p$ divides $30q-1$ and $q$ divides $30p-1$.
Problem
Source: Bosnia and Herzegovina TST 2013 problem 4
Tags: inequalities, symmetry, number theory proposed, number theory
20.05.2013 20:52
Clearly we need $p\neq q$. Then $pq \mid 30p + 30q - 1$, so $pq \leq 30p + 30q - 1$. This writes as $(p-30)(q-30) \leq 899$, and some casework follows.
21.05.2013 10:01
Here my solution: Let $30p+30q-1=kpq$. We have that $k<30$ and $gcd(30,k)=1$ $ \Rightarrow $ $k=${$1,7,11,13,17,19,23,29$}. We have easily that $p\ge 7$ and $q\ge 7$ and $p\not = q$. So, if $k\ge 13$ then $k(p-1)(q-1) > (p+11)(q+11) $. Because, $k>9$ and $3(p-1)\ge p+11$, $3(q-1)\ge q+11$. Hence, \[ k(p-1)(q-1)=(30-k)(p+q)+k-1>(p+11)(q+11) \] and \[ 17(p+q)+28 > (p+11)(q+11) \] $ \Rightarrow $ $(p-6)(q-6)+47 < 0$, contradiction. We have \[ k=1,7,11. \] 1) k=1; $(p-30)\cdot (q-30)=899$ $ \Rightarrow $ $(p;q)=(59;61),(61;59),(31;929),(929;31)$ 2) k=7; $(7p-30)\cdot (7q-30)=893$ $ \Rightarrow $ $(p;q)=(7;11),(11;7)$ 3) k=11; $ (11p-30)\cdot (11q-30)=889 $ $ \Rightarrow $ no solution. answer: $(p;q)=(7;11),(11;7),(59;61),(61;59),(31;929),(929;31).$
21.05.2013 11:19
Great mathuz!!! I was dealing with this problem and found that pq|30p+30q-1 but i didn't proceed like you... However, your solution can be simplified. kpq = 30p+30q-1 < 30p+30q+5p+5q = 35p+35q = 5*7p+5*7q <= 5pq+5pq =10pq Thus resulting in k<10 ... THE REST IS HISTORY...
26.05.2013 11:34
mathuz wrote: Here my solution: Let $30p+30q-1=kpq$. Another variation of this solution. First notice that the equation is symmetric, i.e. if $(p,q)$ is solution then $(q,p)$ is also solution. As mathuz did, we check $k=1$, and since the cases $k=3$ and $k=5$ are impossible we set $k\geq 7$. So $30p+30q-1=kpq\geq 7pq$. We divide the inequality by $pq$ : \[\frac{30}{q}+\frac{30}{p}-\frac{1}{pq}\geq 7\] By symmetry we can assume that $p\leq q$, then $\frac{1}{p} \geq \frac{1}{q}$. So we have $ 7 \leq \frac{30}{q}+\frac{30}{p}-\frac{1}{pq}\leq \frac{60}{p}-\frac{1}{p^{2}} < \frac{60}{p}$. So $p< \frac{60}{7}.$ We just check the cases and we're done.
23.12.2016 00:06
thanks a lot for good solutions