Extended Euclidean algorithm issue. This question is related to RSA cryptosystem.
For simplicity I will work through the example given on Wikipedia on the following address:
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example (under the example header)
under the subheading: "Compute d, the modular multiplicative inverse of e (mod λ(n))" I have done the following which has given me the wrong answer.
Can someone please correct me in stating what I've done wrong or not yet done. Thank you.
p=61 and q=53    
n = pq = 3233    
(this other value confuses me, why is it calculated?) LCM of (60,52) = 780. I'm sure other examples used  n for this??   
e= 17

calculating d
To do this the modular multiplicative inverse of e(mod(n)) must be found.
The worked example give the formula d * e % n = 1
Thus d * 17 % 780 = 1
To solve d here I tried to use Extended Euclidean algorithm here is what I get:
GCD(17, 780)

780 = 45 * 17 + 15
 17 =  1 * 15 +  2 
 15 =  7 *  2 +  1  <<<< Final one as the next remainder is 0

  1 = 15 -  7 *  2
  1 = 15 -  7 * (17-1*15)
  1 =  8 * 15 -  7 * 17
  1 =  8 * (780 - 45 * 17) - 7 * 17
  1 =  8(780) - 367(17)

This is not what I need for d
edit: d in this instance should  be 413
Edit 2, let me run through a whole example I had earlier and set out my concerns more clearly:


*

*P1 picks two primes p and q
p=17
 q=19
 n = pq = 323

*P1 chooses another prime e
e = 7

*P1 makes n and e public

*P2 wants to send P1 'H', 'H' in Ascii is 72

*P2 does the following 72^e % 323 = c. 72^7 % 323 = c = 13

*P2 sends P1 c

*P1 needs to use p and q to decrypt c

*P1 calculates D in order to do so.

*(7xD)(mod((p-1)*(q-1)))=1

*(7xD)(mod((16)*(18))) = 1

*(7xD)(mod(288) = 1

*which is the same as 7*D = 1 mod 288 << Am I correct there?


Extended Euclidean algorithm

GCD(7, 288)

288 = 41 * 7 + 1
7 =  7 * 1 + 0



288 = 41 * 7 + 1 << (no winding up??)


(Something happens here which I am unsure of)


*

*D = 247

*To decode the message c^D mod n is used

*13^247 mod 323 = 72

*72 in Ascii = 'H'

 A: You made a mistake in the last line of your calculation: $8\cdot 45 + 7$ is not equal to $343$.
There is an easier and less error-prone way to do this calculation.
The idea is to write equations $z = 780x + 17y$ and to combine them until we get an equation with $z=\gcd(780,17)=1$
You start with the obvious two equations:
$780 = 780\cdot 1 + 17\cdot 0$
$17 = 780\cdot 0 + 17\cdot 1$
Since $\lfloor 780/17\rfloor=45$, subtract $45$ times the second equation from the first:
$15=780\cdot 1 - 17\cdot 45$
and continue doing this until the left-hand side becomes $1$.
In fact, you don't need to write all the equations in full; you can simply make a table with the values of $z$, $x$ and $y$.
Note that $-367\equiv 413\pmod{780}$
Concerning the value of $n$.
In the article, $n = pq$ is the public modulus. It is used for encryption and decryption: you encrypt $M$ as $M^e\pmod{n}$. The value $\mbox{lcm}(p-1,q-1)$ is used when you prepare your public key: after you choose $p$ and $q$, you choose a public key $e$ and compute your private key $d$ as you did. You do this only once.
You need to have $M^{ed}\equiv M\pmod{pq}$, which is equivalent to $M^{ed}\equiv M\pmod{p}$ and $M^{ed}\equiv M\pmod{q}$.
By Fermat's Little theorem, if $p$ is prime and $\gcd(a,p)=1$, $a^{p-1}\equiv 1\pmod{p}$.
This means that you must have $ed\equiv 1\pmod{p-1}$ and $ed\equiv 1\pmod{q-1}$. This implies that you must have $ed\equiv 1\pmod{\mbox{lcm}(p-1,q-1)}$.
On the other hand, if you find $ed\equiv 1\pmod{(p-1)(q-1)}$, this will imply the previous condition. However, you may find a larger value for $d$, but the value will be the same $\pmod{\mbox{lcm}(p-1,q-1)}$. In that case, the algorithm will still work. However, the number of operations required to compute $M^d\pmod{pq}$ will be larger. As we are dealing with very large numbers, this is significant.
