# Significance of Extended Euclidean Algorithm in Cryptography

I'm currently reading Paul Garrett's book "Making, Breaking Codes", where he goes through the standard textbook implementations of different crypto-systems (RSA, Elgamal etc).

When he talks about the different attacks that can be performed on these systems, he often uses the extended euclidean algorithm on different numbers to perform these attacks.

For example, when talking about an RSA attack where an actor sends the same cipher text to two different people with the exponent $e$ changed, he talks about how you can calculate the $\mathrm{Ciphertext}^{-1} \mod n$ (along with other operations) to find the plain text message. I understand that using the extended Euclidean algorithm will give you an $a$ and $b$ such that $ax + by = 1$, however I'm unclear as to how this can help one solve different problems in cryptography.

How does finding this $ax + by = 1$ help in the solution to different cryptographic problems?