Let $p$, $q$ be prime numbers such that $n^{3pq} – n$ is a multiple of $3pq$ for all positive integers $n$. Find the least possible value of $p + q$.

Question

Recently a exam called PRMO 2017 was conducted. Question 28 went as follows,

Let $p$, $q$ be prime numbers such that $n^{3pq} – n$ is a multiple of $3pq$ for all positive integers $n$. Find the least possible value of $p + q$.

This question was considered to be quite tough. Many people are saying it was too tough to be put in a exam which is open for 14 year olds.

How can it be solved?

I have not studied number theory, so I really couldn't attempt this.

Thanks.

Answer 1

$\color{Green}{\text{Lemma}}$:

• For every odd prime number $p$; and for every positive integer $\alpha$;
  the multiplicative group $\mathbb{Z}_{p^{\alpha}}^*$;
  is a cyclic group of order $\phi(p^{\alpha})= (p-1)p^{\alpha-1}$.
  In other words:

$$ \big( \mathbb{Z}_{p^{\alpha}}^* \ , \times \big) \equiv \big( \mathbb{Z}_{(p-1)p^{\alpha-1}} \ , + \big) . $$

• For $\color{Red}{p=2}$; and for every positive integer $\color{Red}{3 \leq \alpha}$;
  the multiplicative group $\mathbb{Z}_{2^{\alpha}}^*$;
  is the direct sum of $\mathbb{Z}_2$ and a cyclic group of order $\color{Red}{\dfrac{1}{2}}\phi(2^{\alpha})= \color{Red}{2^{\alpha-2}}$.
  In other words:

$$ \big( \mathbb{Z}_{2^{\alpha}}^* \ , \times \big) \equiv \big( \mathbb{Z}_2 \oplus \mathbb{Z}_{\color{Red}{2^{\alpha-2}}} \ , + \big) . $$

• The multiplicative group $\mathbb{Z}_{2^2}^*$; is a cyclic group of order $2$.
  The multiplicative group $\mathbb{Z}_{2}^*$; is the trivial group.

---

---

If $n$ is coprime with $3pq$ then we can factor $n$ and hence we have: $$ n^{3pq }\overset{3pq}{\equiv}n \Longrightarrow n^{3pq-1}\overset{3pq}{\equiv}1 . $$

---

---

First case: All of $3, p, q$ are different. By the above lemma, we know that:
there is an integer $a$; with $\text{ord}_p(a)=p-1$.
On the otherhand $a^{3pq-1}\overset{p}{\equiv}1$;
which implies that $\color{Blue}{p-1 \mid 3pq-1}$.

Similarly one can prove that $p-1 \mid 3pq-1$ and $3-1 \mid 3pq-1$.

---

But notice that $\color{Blue}{3pq-1=3(p-1)q}+\color{Purple}{3q-1}$;
similarly we have: $3pq-1=3p(q-1)+3p-1$
and $3pq-1=2pq+pq-1$.

So we can conclude that:

$$ \color{Blue}{p-1 \mid} \color{Purple}{3q-1} \ \ \ \ \text{and} \ \ \ \ q-1 \mid 3p-1 \ \ \ \ \text{and} \ \ \ \ 3-1 \mid pq-1 ; $$

the last divisibility condition implies that both of $p,q $ must be odd;
you can check that $p=11 , q=17$ satisfies the above divisiblity conditions.

---

Why these are the least posible values?

$ \color{Green}{ \text {As} \ \color{Red}{\text{@Thomas Andrews}} \ \text{has been mentioned:} \\ \color{Red}{\text{"}} \text {we can assume} \ p \overset{6}{\equiv} 5 \ . \\ \text {[ Because} \ p−1∣3q−1 \ \text {means} \ p−1 \ \text {is coprime to} \ 3 \ ; \text {so} \ p \overset{3}{\ncong} 1; \ \text {which implies} \ p \overset{3}{\equiv} 2 \ \text {. ]} \\ \text {Notice that} \ p=5 \ \text {doesn't work,} \\ \text {since} \ 3p−1=14 \ \text {is not divisible by} \ q−1 \ \text {for any} \ q \overset{6}{\equiv} 5. \ \\ \text {So the smallest possible values for} \ p,q \ \text {is} \ 11,17 \ .} \color{Red}{\text{"}}$

---

---

Second case: All of $3, p, q$ are not distict. We will show that this second case is impossible.

• $p=3$ or $q=3$.
  From assumtion of problem we know that:
  $3^{3pq} \overset{9}{\equiv} 3$; so we have: $0 \overset{9}{\equiv} 3^2 \overset{9}{\equiv} 3$;
  which is an obvious contradiction.

• $p=q$.
  From assumtion of problem we know that:
  $p^{3pq} \overset{p^2}{\equiv} p$; so we have: $0 \overset{p^2}{\equiv} p^2 \overset{p^2}{\equiv} p$;
  which is an obvious contradiction.

Answer 2

This is not an answer for a beginner. However, Part (a) of this more general result can be used, although a proof is left as an exercise. As defined in that link, we have $$3pq \mid g(3pq,1)\,,$$ so $g(3pq,1)>2$. Hence, $3pq-1$ must be even and $$g(3pq,1)=2\,\prod_{r\in D(3pq,1)}\,r\,,$$ where $D(3pq,1)$ is defined in the same link above. It follows that $p,q\in D(3pq,1)$ are odd primes. That is, $p-1\mid 3pq-1$ and $q-1\mid 3pq-1$. The rest goes as Famke suggests (i.e., by observing that $3$, $p$, and $q$ must be distinct odd primes with $p-1\mid 3q-1$ and $q-1\mid 3p-1$).