-2
$\begingroup$

Really simple question regarding the Affine Cipher.

Can someone tell me how $3^{-1}$ is supposed to result in 9 in the following explanation below?

enter image description here

$\endgroup$
  • $\begingroup$ 27 ≣ 1 (mod 26) and 3*9 = 27. Gotta pay attention to the modulus. $\endgroup$ – Chib Nov 6 '16 at 3:42
2
$\begingroup$

If you want to find the multiplicative inverse of an integer a (mod n) you can use the extended Euclidean algorithm. For two integers a and b, the Extendend Euclidean Algorithm not only calculate the greatest common divisor d but also two integers x and y that satisfy the following equation:

ax + by = d = gcd(a,b) (where gcd is the greatest common divisor)

So if a and b are relatively prime (gcd(a,b)=1), x is the multiplicative inverse of a (mod y), and y is the multiplicative inverse of b (mod x).

Wikipedia seems to provide a good explanation of the algorithm

Hope I was helpful!

$\endgroup$
  • $\begingroup$ The wikipedia article regarding "Modular multiplicative inverse" helped me to bring some light into the topic - the Euclidean algorithm will be covered later in the book. Thanks anway! $\endgroup$ – HansMusterWhatElse Mar 10 '16 at 15:47
  • $\begingroup$ Good!! I thought you wanted to find the multiplicative inverse of an integer (mod n). Was I wrong? $\endgroup$ – ssh3ll Mar 10 '16 at 17:51

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.