Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 0 down vote accepted

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.


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


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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.