I want to prove that given a certain $\alpha$, its modular inverse with respect of 26 ranges between [0,25].

Can you give me an hint ?

  • 1
    $\begingroup$ All integers, whether or not they're anyone's inverse, will live in $[0,25]$ when you work mod 26. $\endgroup$
    – Randall
    May 6, 2019 at 14:25
  • $\begingroup$ To be more exact, all integers belong to an equivalence class $[a] = \{a + 26\Bbb Z\}$, and $a$ can be chosen to be in $[0, 25]$ if you like. $\endgroup$
    – Théophile
    May 6, 2019 at 14:28
  • $\begingroup$ You can just try them all in a spreadsheet. There will only be one when $a$ is coprime to $26$, so has no factors $2$ or $13$. If the modulus is too large to try them all, the extended Euclidean algorithm is what you need. $\endgroup$ May 6, 2019 at 14:29
  • $\begingroup$ If you are attempting to prove that every natural $< 26$ occurs as an inverse then this statement is not true, because $a$ is invertible $\!\bmod n\iff \gcd(a,n)=1\ $ (by Bezout). $\endgroup$ May 6, 2019 at 14:33
  • $\begingroup$ @Randall can you explain me why ? $\endgroup$
    – AleWolf
    May 6, 2019 at 16:22


You must log in to answer this question.

Browse other questions tagged .