# Find odd primes $p$ and $q$ such that $(p-1)\mid {3q-1}$ and $(q-1)\mid{3p-1}$.

Find odd primes $$p$$ and $$q$$ such that $$(p-1)\mid {3q-1}$$ and $$(q-1)\mid{3p-1}$$.

My progress till now: I got $$p=11$$ and $$q=17$$ as a solution satisfying this question. Can anyone give me some hints rather than a solution ? Thanks in advance .

• There are also some smaller ones... Are you supposed to find all the solutions, or is it enough to find one (in which case you are already done)? Jul 26, 2020 at 4:16
• oh , yes.. I meant odd primes Jul 26, 2020 at 4:19
• @RobertIsrael I am supposed to find all the solutions . Jul 26, 2020 at 4:21
• $3$ and $3$, $3$ and $5$. Jul 26, 2020 at 4:24
• artofproblemsolving.com/community/q1h39774p257111 Jul 26, 2020 at 4:26

The condition tells us that $$\frac{3p-1}{q-1}$$,$$\frac{3q-1}{p-1}$$, and $$\frac{3p-1}{p-1} \frac{3q-1}{q-1}$$ is an integer. However, for $$p,q\ge5$$, we have

$$\frac{3p-1}{p-1} \frac{3q-1}{q-1} < \frac{3p}{\frac{4}{5}p} \times \frac{3q}{\frac{4}{5}q} <15$$

Here's a hint: When you have a problem like this, with two separate divisibilities, you want to make the right sides look the same. In particular, here $$p-1|3q-1+3(p-1)=3p+3q-4,$$ and $$q-1$$ must also divide this by symmetry. As a result, $$\operatorname{lcm}(p-1,q-1)|3p+3q-4.$$ The left side should be larger than the right side for most $$(p,q)$$ as long as $$p-1$$ and $$q-1$$ can't share big factors, which would allow you to finish; can you determine whether $$p-1$$ and $$q-1$$ can share large factors?

• I am sorry, but can you explain this line? " for most (𝑝,𝑞) as long as 𝑝−1 and 𝑞−1 can't share big factors," Jul 26, 2020 at 4:39
• If you can show that $p-1$ and $q-1$ have few common factors (say, can only have factors bounded by $k$), then $\operatorname{lcm}(p-1,q-1)\geq \frac{(p-1)(q-1)}{k}$, and the left side is too large compared to the right. Jul 26, 2020 at 4:52

Let $$3q-1 = k(p-1)$$. Try $$k=1,2,3,\ldots$$ until you can show $$k$$ is too large.

• but q is not fixed , so how can we show that k is too large .. Jul 26, 2020 at 4:33
• Let's say $q \le p$. $$k = \frac{3q-1}{p-1} \le \frac{3p-1}{p-1} = 3 + \frac{2}{p-1}.$$ How big can this be? Jul 26, 2020 at 15:40