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

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!

• Actually $T$ needs to divide $$[p-1,q-1]$$ – lab bhattacharjee Mar 19 at 6:54
• As lab mentions, there is a stronger result that holds which is $T\mid\operatorname{lcm}(p-1,q-1)$; the proof is similar using Carmichael's lambda function instead of Euler's totient function. $$T\mid\lambda(pq)=\operatorname{lcm}(\lambda(p),\lambda(q))=\operatorname{lcm}(p-1,q-1)$$ The conclusion desired in the question is a corollary of the above result since $\lambda(n)\mid\varphi(n)$ for all natural numbers $n$. – learner Mar 19 at 7:16

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.

• May I ask what ord𝑛(𝑥) is referring to? I haven't seen that notation before. – Sania Mar 19 at 6:55
• $\text{ord}_n(x)$ is the order of $x$ modulo $n$, that is, $\text{ord}_n(x)$ is the smallest positive integer $t$ such that $x^t\equiv 1$ modulo $n$. – boaz Mar 19 at 6:56
• I see, thanks so much! – Sania Mar 19 at 6:57

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