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 ?
Asked
Active
Viewed 60 times
0
-
1All integers, whether or not they're anyone's inverse, will live in $[0,25]$ when you work mod 26. – Randall May 06 '19 at 14:25
-
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. – Théophile May 06 '19 at 14:28
-
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. – Ross Millikan May 06 '19 at 14:29
-
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). – Bill Dubuque May 06 '19 at 14:33
-
@Randall can you explain me why ? – AleWolf May 06 '19 at 16:22
-
Every integer is congruent to something mod 26: just long-divide by 26 and take the remainder. – Randall May 06 '19 at 16:25