6
$\begingroup$

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 .

$\endgroup$
7
  • 3
    $\begingroup$ 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)? $\endgroup$ Jul 26 '20 at 4:16
  • $\begingroup$ oh , yes.. I meant odd primes $\endgroup$ Jul 26 '20 at 4:19
  • $\begingroup$ @RobertIsrael I am supposed to find all the solutions . $\endgroup$ Jul 26 '20 at 4:21
  • 1
    $\begingroup$ $3$ and $3$, $3$ and $5$. $\endgroup$ Jul 26 '20 at 4:24
  • 2
    $\begingroup$ artofproblemsolving.com/community/q1h39774p257111 $\endgroup$
    – Adola
    Jul 26 '20 at 4:26
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I am sorry, but can you explain this line? " for most (𝑝,𝑞) as long as 𝑝−1 and 𝑞−1 can't share big factors," $\endgroup$ Jul 26 '20 at 4:39
  • $\begingroup$ 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. $\endgroup$ Jul 26 '20 at 4:52
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ but q is not fixed , so how can we show that k is too large .. $\endgroup$ Jul 26 '20 at 4:33
  • 2
    $\begingroup$ 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? $\endgroup$ Jul 26 '20 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.