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

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.

Solutions Collecting From Web of "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$."

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

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