I'm struggling in a specific step in the Extended Euclidean Algorithm (EEA) while trying to find the value for d in the private key of the RSA Cryptosystem.
**Calculation of
d = e^(−1) mod φ(n) = 49−1 mod 640 using EEA:
640 = 13 · 49+3
49 = 16 · 3+1
⇔ 1 = 49−16 · 3
= 49−16(640−13 · 49)
= 209 · 49−16 · 640 // the problem
⇒ 49−1 mod 640 ≡ 209.**
How was this equation 49−16(640−13 · 49) converted to 209 · 49−16 · 640 ?
From where did the 209 came?