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