[Math] 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$.

elementary-number-theoryprime numbers

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.

Best Answer

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

Related Question