Problem : Let $p$, $q$ two distincts prime numbers and $n=pq$. Let $e$ be a prime number such that $\gcd( (p-1)(q-1),e) = 1$ and $d$ such that $ed=1+k(p-1)(q-1)$. Let $A \in \mathbb { Z } / n$. Show that $A ^ { e d } \equiv A \pmod p$.

My solution : We have that $ed \equiv 1 (\bmod p-1)$. Thus by Fermat's little theorem:

$A ^ { e d } \equiv A^{k(p-1)+1} \equiv A^{k(p-1)}A^{1} \equiv ({A^{p-1}})^{k}A \stackrel{\text{Fermat}}{\equiv} 1^k A \equiv A \pmod p$.

Question : Does the reasoning seems correct? Am I missing some steps?

  • 2
    $\begingroup$ I would only suggest to choose another letter (not $k$) , but besides this : perfect solution. $\endgroup$ – Peter Apr 13 at 7:36
  • $\begingroup$ @Peter Awesome, thank you very much! $\endgroup$ – NotAbelianGroup Apr 13 at 7:43

Your Answer

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

Browse other questions tagged or ask your own question.