1
$\begingroup$

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.

  • 0
    We are interested in all $p$ and $q$ such that the residue equivalency holds for all $a$.2012-10-22

1 Answers 1

0

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

  • 0
    I realized that it does not work for all $l,m$ such that $l\ne m$, for instance the when $l=1$, $m=3$, $11$ and $23$ does not satisfy the congruence... any suggestion?2012-11-02