# Possible primes $p$ $q$ satisfying $a^{3pq}-a \equiv 0 \pmod {3pq}$

For any integer $a$, consider the primes $p$ and $q$ satisfying

$a^{3pq}-a \equiv 0 \pmod {3pq}$

Find all such possible $p$ and $q$.

So I tried breaking it down into 3 congruences:

$a^{3pq}-a \equiv 0 \pmod {3}$

$a^{3pq}-a \equiv 0 \pmod {p}$

$a^{3pq}-a \equiv 0 \pmod {q}$

and for $a^{3pq}-a \equiv 0 \pmod {p}$ it is equivalent to $a^{3pq-1}-1 \equiv 0 \pmod {p}$ since $gcd(a,p)=1$

and I would have $Ord_p(a) \mid (3pq-1)$

But I still cannot see by far how I can approach the final solution in this way.

-
For fixed $p$ and $q$, should the statement hold for all $a$? Or are you interested in finding $p$ and $q$, given $a$? –  TMM Oct 22 '12 at 8:55
We are interested in all $p$ and $q$ such that the residue equivalency holds for all $a$. –  fmat Oct 22 '12 at 22:53

Let us consider $n=\prod P_i^{A_i}$ and $(a,n)=1$ where $P_i$s are distinct primes.

If $a^n\equiv a\pmod n,a^{n-1}\equiv 1\pmod n\implies a^{n-1}\equiv 1\pmod {P_i^{A_i}}$

But, $P_i^{A_i}$ has primitive root, so there exists $a$ such that $ord_{(P_i^{A_i})}a=\phi(P_i^{A_i})=P_i^{A_i-1}(P_i-1)$.

So, $P_i^{A_i-1}(P_i-1)$ must divide $(n-1)=(\prod P_j^{A_j}-1)$ which is impossible if $A_i-1\ge 1$ as $(P_i^{A_i-1},\prod P_j^{A_j}-1)=1$.

This is true for $P_i\mid n$, so, $n$ reduces to $\prod P_i$

and $(P_i-1)$ must divide $(\prod P_j-1)$

Now $\prod P_j-1=(P_i-1)(\prod_{i\ne j} P_j-1)+(\prod_{i\ne j} P_j-1)$

$(P_i-1)$ must divide $(\prod_{i\ne j} P_j-1)$

In that case, $a^{n-1}\equiv 1\pmod {P_i}$

$\implies a^{n-1}\equiv 1\pmod {lcm(P_i)}$

But, $lcm(P_i)=\prod P_i$ as $(P_i,P_j)=1$ for $i\ne j$, so $lcm(P_i)=n$

$\implies a^{n-1}\equiv 1\pmod n$, which has $(P_i-1)\mid (\prod_{i\ne j} P_j-1) ∀ P_k\mid n$ as necessary and sufficient condition known as Korselt's Criterion.

Here, $P_1=3,P_2=p,P_3=q \implies p,q,3$ are all distinct primes.

So,

(i)$(3-1)\mid(pq-1)\implies pq$ is odd, So, $p,q\ne 2$

(ii)$(p-1)\mid(3q-1)$

Now, $3$ must not divide $(p-1)$ as it does not divide $(3q-1),$

So, $p-1=3a+1,3a-1$ for some integer $a$

But $p\ne 3a$ as prime $p>3,$ so odd $p=3a+2$, so a must be odd $=2b+1$(say).

So, $p=3a+2=3(2b+1)+2=6b+5$

(iii) $(q-1)\mid (3p-1),$ so $q$ will also be $\equiv 5\pmod 6$

As we need to test for any integer $a,$ it suffices to test for $(a,3pq)=1$.

By trial, one set of values of $p,q$ is $17,11$.

-
Good, so I would like to know if I am following my own approach how would that lead me to the final solution? –  fmat Oct 30 '12 at 18:29
@fmat, $ord_pa\mid (3pq-1)$ and if $a$ is a primitive root, which exists for all primes, $ord_pa=p-1\implies (p-1)\mid(3pq-1)$, but $3pq-1=3q(p-1)+3q-1,$ so, $(p-1)\mid(3q-1),$ same for $3$ and $q$. –  lab bhattacharjee Oct 30 '12 at 18:55
Yes that was what I ended up getting, but don't those divisibility relationships only apply to those $a$'s that are primitive roots of $p$ (or $q$) then? I am a bit confused by myself here. –  fmat Oct 30 '12 at 22:54
@fmat, we need to find $p,q$ for any integer $a$ which must satisfy for the primitive roots,too. Now if $(a,p)=1, ord_pa$ must divide $\phi(p)=p-1\implies lcm(ord_pa)\mid (p-1),$ in particular for the primitive root $a,ord_pa=p-1$. –  lab bhattacharjee Oct 31 '12 at 5:04
I see, so now I have $(p-1)\mid(3q-1)=3(q-1)+2$, $(q-1)\mid(3p-1)=3(p-1)+2$, I am thinking of writing as: $3(q-1)+2 = r(p-1)$ and $3(p-1)+2 = s(q-1)$ for some $r,s\in\Bbb N$ and by combining the two equations I got $(r+3)(p-1)-(s+3)(q-1)=0$. Does every $p,q$ satisfying this equation qualify? –  fmat Oct 31 '12 at 6:02