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
    For fixed $p$ and $q$, should the statement hold for all $a$? Or are you interested in finding $p$ and $q$, given $a$?2012-10-22
  • 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
    Good, so I would like to know if I am following my own approach how would that lead me to the final solution?2012-10-30
  • 0
    @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$.2012-10-30
  • 0
    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.2012-10-30
  • 0
    @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$.2012-10-31
  • 0
    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?2012-10-31
  • 0
    @fmat, does $(r+3)(p-1)=(s+3)(q-1)$ imply $3(q-1)+2=r(p-1)$ and $3(p-1)+2=s(q-1)$, one counter-example: $(p,q,r,s)=(5,11,7,1)$.2012-10-31
  • 0
    I see, so one does not imply the other; but toward getting all the $p,q$ is there any other hint?2012-10-31
  • 0
    @fmat, I'd glad to share something more than hint if I had one. I tried to solve for $p,q$ with $3q-1=r(p-1),3p-1=s(q-1),$ and got $q=\frac{2r+rs-3}{sr-9}=1+\frac{2r+6}{sr-9}$ and similar expression for $p,$ but it did not lead me much further.2012-11-01
  • 0
    Thank you for trying to help, so I got to the same result as $p=6l+5$ and $q=6m+5$ for some $l,m\in\Bbb N$ while $l \ne m$. I am just wondering if all $p,q$ in this form satisfy the given congruence?2012-11-02
  • 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