Numbers $a^{p}a^q$ congruent to 1 modulo pq

556 Views Asked by At

Consider numbers of the form $a^{p}a^q=a^{p+q} $ where $p,q$ are primes.
Now I'm interested when such number is congruent to $1$ modulo product $pq$.

Take for example $p=3$ and $q=5$.
Then it seems that every number $a$ coprime with $p$ and $q$ is congruent to $1$ modulo $(pq)$.

For example
$7^8-1 \equiv 1 \pmod{15} , \ \ 11^8-1 \equiv 1 \pmod{15}, \ \ 13^8-1 \equiv 1 \pmod{15} , \ \dots\ \ \ 601^8-1 \equiv 1 \pmod{15} $ etc...

If we take $p=5$ and $q=7$ we have
$7^{12}-1 \equiv 1 \pmod{35} , \ \ 11^{12}-1 \equiv 1 \pmod{35} , \ \ 13^{12}-1 \equiv 1 \pmod{35}$, etc...

I don't know whether it is true for all $a$ but for pairs $(p,q)=\{(3,5),(5,7)\}$ I have found no exceptions.

One could think that for others pairs of primes situation is similar however for pairs like $(11,13)$ or $(17,19)$ the pattern is not repeating.

For example $7^{11 + 13} \ \equiv 14 \pmod {11 \cdot 13}, \ 17^{11 + 13} \ \equiv 53 \pmod {11 \cdot 13} $.

So my question:

  • What are conditions imposed on pairs $(p,q)$ for which $a^{p+q} \equiv 1 \pmod {pq}$ holds?

  • Why it holds for $(3,5)$ and $(5,7)$, ... for others probably not?

1

There are 1 best solutions below

10
On BEST ANSWER

This is a partial answer.

  • Why it holds for $(3,5)$ and $(5,7)$, ... for others probably not?

Let us prove that $a^{3+5}\equiv 1\pmod{3\times 5}$ if $\gcd(a,3\times 5)=1$.

We have$$a^{3+5}-1=a^8-1=(a-1)(a+1)(a^2+1)(a^4+1)$$

  • If $a\equiv 1\pmod 3$, then $a-1\equiv 0\pmod 3$

  • If $a\equiv 2\pmod 3$, then $a+1\equiv 0\pmod 3$

  • If $a\equiv 1\pmod 5$, then $a-1\equiv 0\pmod 5$

  • If $a\equiv 2,3\pmod 5$, then $a^2+1\equiv 0\pmod 5$

  • If $a\equiv 4\pmod 5$, then $a+1\equiv 0\pmod 5\qquad\blacksquare$

Next, let us prove that $a^{5+7}\equiv 1\pmod{5\times 7}$ if $\gcd(a,5\times 7)=1$.

We have $$a^{5+7}-1=a^{12}-1=(a-1)(a^2+a+1)(a^3+1)(a^6+1)$$

  • If $a\equiv 1\pmod 5$, then $a-1\equiv 0\pmod 5$

  • If $a\equiv 2,3\pmod 5$, then $a^6+1\equiv 0\pmod 5$

  • If $a\equiv 4\pmod 5$, then $a+1\equiv 0\pmod 5$

  • If $a\equiv 1\pmod 7$, then $a-1\equiv 0\pmod 7$

  • If $a\equiv 2,4\pmod 7$, then $a^2+a+1\equiv 0\pmod 7$

  • If $a\equiv 3,5,6\pmod 7$, then $a^3+1\equiv 0\pmod 7\qquad\blacksquare$


As lab bhattacharjee commented, Carmichael Function $\lambda(n)$ might help.

$\lambda(n)$ is defined as the smallest integer such that $a^{\lambda(n)}\equiv 1\pmod n$ where $\gcd(a,n)=1$.

So, we can say that $$\text{$p+q\ $ is divisible by $\lambda(pq)\quad\iff\quad a^{p+q}\equiv 1\pmod{pq}$}$$

For example, $$a^{3+5}\equiv 1\pmod{3\times 5}\quad\text{and}\quad a^{5+7}\equiv 1\pmod{5\times 7}$$ follow from $$\lambda(3\times 5)=4\quad\text{and}\quad \lambda(5\times 7)=12$$ which can be seen at OEIS A002322.


Added :

If $q=p$, then $$\lambda(pq)=\lambda(p^2)=p(p-1)$$ So, $$\lambda(pq)\mid p+q\implies p(p-1)\mid 2p\implies p=2,3$$ and it is easy to see that $a^{2+2}\equiv 1\pmod{2\times 2}$ and $a^{3+3}\equiv 1\pmod{3\times 3}$.

So, if $q=p$, $(p,q)=(2,2),(3,3)$ are the only such pairs.

If $q\not=p$, then $$\lambda (pq)=\text{lcm}(\lambda(p),\lambda(q))=\text{lcm}(p-1,q-1)$$ So, $$\lambda(pq)\mid p+q\implies \text{lcm}(p-1,q-1)\mid p+q$$

So, if $q\not =p$, then in order to have $a^{p+q}\equiv 1\pmod{pq}$, we have to have $$\text{lcm}(p-1,q-1)\mid p+q$$