modular arithmetic - One variable modulo equation

I was attempting Wiener's Attack on RSA with a simple example and I came to a one variable modulo equation which I managed to solve with brute-force but I think it must be easier than that with some algorithm/formula.

here it is.

$e * d \equiv 1 \mod phi(N)$

e and phi(N) are known: e = 5 550 641 and phi(N) = 15 726 816

so it gives us: $5 550 641 * d \equiv 1 \mod phi(N)$

I got the answer, d = 17 but as I mentioned only with brute force, is there any formula or algorithm for solving this equation?

Answer

Solving $5550641 d \equiv 1 \pmod{15726816}$ can be done very quickly. This is called finding the modular inverse of $5550641$ modulo $15726816$. The best way to do this is through the Euclidean Algorithm (along with back substitution. This is sometimes called the Extended Euclidean Algorithm).

This is a topic that has been asked extensively on this site, so I will link you to some examples.

1. In Modular Inverses it is asked to find the modular inverse of $19$ mod $141$. This is the same question as yours, but with different numbers.


2. In Using Extended Euclidean Algorithm for $85$ and $45$ we have another example with still different numbers.


3. In How to use the Extended Euclidean Algorithm manually? some details are given in a more general context, with an eye towards computing by hand. I'll note that in your case, you should really use a computer. But I'm assuming that you want to understand, as otherwise you could just prompt wolframalpha.

Good luck!