Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove that $T\mid(p-1)(q-1)$.

Question

Suppose that $p$ and $q$ are distinct primes and that $m$ is an integer satisfying $\gcd(m, pq) = 1$. Suppose that $T$ is the smallest positive integer satisfying $m^{T}\equiv \pmod {pq}$. Prove that $T\mid(p-1)(q-1)$.

I know that this is RSA encryption, but how do I go about proving this?

Thanks!

Answer 1

By the Euler's theorem, if $\gcd(x,n)=1$, then $$ x^{\varphi(n)}\equiv 1\ (\text{mod}\,n) $$ Therefore, $\text{ord}_n(x)\mid \varphi(n)$. In particular, for $n=pq$, $x=m$ and $T=\text{ord}_n(m)$ we obtain $$ T\mid \varphi(pq)=(p-1)(q-1) $$
as required.

Answer 2

The proof is simple:

We have $\gcd(m, pq) = 1$, then Euler Theoreme say:

$$m^{(p-1)(q-1)} \equiv 1 \pmod{pq}$$

You Defined $T$ as the smallest number verify : $m^{T} \equiv 1 \pmod{pq}$ with $T\neq 0$

Then using euclidian division of $(p-1)(q-1)$ by $T$ :

$$(p-1)(q-1) = T n + r , \quad 0 \leq r < T$$

Then:

$$m^{r} \equiv 1 \pmod{pq}$$

Then $r=0$ ($T$ is the smallest number verify : $m^{T} \equiv 1 \pmod{pq}$ with $T\neq 0$)

Then $T$ devide $(p-1)(q-1)$