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

3 Answers 3

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$ Commented Jul 26, 2020 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$ Commented Jul 26, 2020 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$ Commented Jul 26, 2020 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$ Commented Jul 26, 2020 at 15:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .