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.
$\color{Green}{\text{Lemma}}$:
$$
\big(
\mathbb{Z}_{p^{\alpha}}^*
\ , \times
\big)
\equiv
\big(
\mathbb{Z}_{(p-1)p^{\alpha-1}}
\ , +
\big)
.
$$
$$
\big(
\mathbb{Z}_{2^{\alpha}}^*
\ , \times
\big)
\equiv
\big(
\mathbb{Z}_2
\oplus
\mathbb{Z}_{\color{Red}{2^{\alpha-2}}}
\ , +
\big)
.
$$
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$).