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

• for what stands PRMO? Aug 21, 2017 at 14:54
• So solutions using number theory are not allowed? Do you know any number theory at all, e.g. Fermat's Little Theorem or Euler's generalization, or modular arithmetic (congruences)? We need more context to write helpful answers. Aug 21, 2017 at 14:55
• @Dr.SonnhardGraubner PRMO stands for the pre-regional mathematics olympiad. It is the first stage in India for those who want to participate in the International Math Olympiad. Students from age 14-17 are allowed. Aug 22, 2017 at 2:19
• @BillDubuque Yes, number theory solutions are allowed. I do know Fermat's Last theorem but that's about it. never heard or Euler's generalization. Aug 22, 2017 at 2:20

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

• $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$;
• You are assuming that $p,q$ and $3$ are pairwise different. The contrary case yeild no solutions, but I think that it still should be considered. Aug 21, 2017 at 15:37
• In particular, you can assume $p\equiv 5\pmod 6$ since $p-1\mid 3q-1$ means $p-1$ is not divisible by $3$. And $p=5$ doesn't work since $3p-1=14$ is not divisible by $q-1$ for any $q\equiv 5\pmod{6}$. So the smallest possible $p,q$ is $11,17$. Aug 21, 2017 at 16:08
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$).