# 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)? Commented Jul 26, 2020 at 4:16
• oh , yes.. I meant odd primes Commented Jul 26, 2020 at 4:19
• @RobertIsrael I am supposed to find all the solutions . Commented Jul 26, 2020 at 4:21
• $3$ and $3$, $3$ and $5$. Commented Jul 26, 2020 at 4:24
• artofproblemsolving.com/community/q1h39774p257111 Commented 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," Commented 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. Commented 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 .. Commented 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? Commented Jul 26, 2020 at 15:40