amparvardi wrote: Find all pairs $(p,q)$ of prime numbers such that \[m^{3pq} \equiv m \pmod{3pq} \qquad \forall m \in \mathbb Z.\] Suppose that $p \le q $ Set $m=-1$ we have : $(-1)^{3pq} \equiv -1 \pmod{3pq} \Rightarrow $ both $p,q$ are odd. Set $m$ satisfy $(m,p)=(m,q)=(m,3)=1 \Rightarrow m^{3pq-1} \equiv 1 \pmod 3pq$ Set $(m,p)=1 \Rightarrow m^{p-1} \equiv 1 \pmod p$ $\Rightarrow p-1 | 3pq-1 \Rightarrow p-1|3q-1$ Set $(m,q)=1 \Rightarrow m^{q-1} \equiv 1 \pmod q$ $\Rightarrow q-1 | 3pq-1 \Rightarrow q-1|3p-1$ We have $\begin{cases} p-1|3q-1 \\ q-1|3p-1 \end{cases} $ Not hard

Let's choose $m$ such that $m$ is a primitive root of p,then this is a primitive root of $q$ too. $m^{3pq-1}\equiv 1\mod p,m^{p-1}\equiv 1\mod p$ So $p-1|3pq-1\implies p-1|3pq-p=p(3q-1),p-1|3q-1$ and similarly $q-1|3p-1$ Let $p=q$ first,then $p-1|3p-1\implies p-1|3p-3\implies p-1|2\implies p=2,3$ Now let $p>q,p-1|3q-1\implies p-1|3q-p$ If $3q-p\ge 2(p-1)\implies 3q\ge 3p-2$ $3q=3p-2\implies 3|2,$so $3p>3q>3p-2,3q=3p-1,$contradiction. $3q-p=p-1\implies 3(q-1)=2p-4|3(3p-1)\implies 2p-4|9p-3,18p-6$ and also $2p-4|18p-36\implies 2p-4|30$ So $2(p-2)=2,p=3$ but $3q=2$ $2(p-2)=6,p=5,3q=6,q=2$ $2(p-2)=10,p=7,3q=10$ $2(p-2)=30,p=17,3q=30$ no solution.

Magical,what if one of $p,q$ is $2$? Also $p-1|3pq-1$ if $ord_p(m)=p-1,$otherwise $m^{gcd(p-1,3pq-1)}\equiv 1\mod p,$not necessarily $p-1|3pq-1$ but you didn't mentioned that,only assumed $pq\not| m$

Sorry,there is a mistake in my calculation. $3q=2p-1,$so when $p=5,q=3$ If $p=17,q=11$ Indeed,they satisfy the condition.Because $17.11.3=561,$a Charmichael number and if $3,5\not| m,m^{44}\equiv 1\mod 3,5$

mathmdmb wrote: Magical,what if one of $p,q$ is $2$? In his first line, he proves that $p, q$ are odd.

I meant $m^n-m$ is always divisible by $2,$so eithe $p$ or $q$ may be $2$.The impossibility hasn't been ruled out.

mathmdmb wrote: Magical,what if one of $p,q$ is $2$? Also $p-1|3pq-1$ if $ord_p(m)=p-1,$otherwise $m^{gcd(p-1,3pq-1)}\equiv 1\mod p,$not necessarily $p-1|3pq-1$ but you didn't mentioned that,only assumed $pq\not| m$ Sorry. I think I am true. $m^{3pq} \equiv m \pmod{3pq}$ is true for all "$m \in \mathbb{Z}$" Ps: $(p,q)=(11,17);(17,11)$

I don't,you missed the solution $(5,3).$And the fact is you aren't completely wrong but while concluding $p-1|3pq-1$ you should choose the convenint $m$.Because otherwise if $ord_p(m)=d|p-1,3pq-1,d<p-1,$it would be true.But after we choose $ord_p(m)=p-1,$it is clear.

Amir Hossein wrote: Find all pairs $(p,q)$ of prime numbers such that \[m^{3pq} \equiv m \pmod{3pq} \qquad \forall m \in \mathbb Z.\] Wlog suppose that $p\leq q$.Choose $m$ such that $ord_{p}(m)=p-1$ then $p | m^{3pq-1}-1$ and so $p-1|3pq-1$ , $p-1|3q-1$.if $p=q$ then $p=q=3$ but $27\nmid 3^{27}-3$ then $p<q$, since $p$ and $q$ are odd ( we choose $m=-1$) we have $p+2 \leq q$ so $3q-3>3p-1$ but $q-1|3p-1$ implies that $3p-1=2q-2$, since $p-1|3q-1$ we have $p-1|9p+1$ and $p-1|10$ so $p=11$ and $q=17.$

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=53564&

mathmdmb wrote: Let's choose $m$ such that $m$ is a primitive root of p,then this is a primitive root of $q$ too.

mathmdmb,how can you be sure that an integer exists which is a primitive root of $p$ as well as $q$.

\bump any other solution ?

1996 Romania TST