2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Actually $T$ needs to divide $$[p-1,q-1]$$ $\endgroup$ – lab bhattacharjee Mar 19 at 6:54
  • $\begingroup$ 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$. $\endgroup$ – learner Mar 19 at 7:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ May I ask what ord𝑛(𝑥) is referring to? I haven't seen that notation before. $\endgroup$ – Sania Mar 19 at 6:55
  • $\begingroup$ $\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$. $\endgroup$ – boaz Mar 19 at 6:56
  • $\begingroup$ I see, thanks so much! $\endgroup$ – Sania Mar 19 at 6:57
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.