# 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?

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!

• Back substitution is not the Extended Euclidean algorithm. The E.E.A. is a special layout which directly outputs the g.c.d. and the coefficients of a Bézout's relation between two numbers (One step further yields the l.c.m.). See for instance my answer to this question. – Bernard Jan 18 '17 at 16:14
• @ mixedmath, Done, Thanks ! – Leonardo Jan 18 '17 at 16:25
• @Bernard The "extended Euclidean algorithm" is an overloaded term that may refer to many different variants of this algorithm (including the common back-substitution method). I do agree however that the augmented form using equations or matrices is better (I present that here in an elementary form) since it is much less error-prone, easier to remember, and motivates generalizations such as (Hermite-)Smith normal form, etc. – Bill Dubuque Jan 18 '17 at 18:36
• @Bernard I prefer the fractional form of the extended Eucldean algorithm, but that's a little tricky for novices. – Bill Dubuque Jan 18 '17 at 18:41
• @Bill Dubuque: It seems like you work within the class group of fractionary ideals. Am I right? – Bernard Jan 18 '17 at 18:57