RSA: Private key calculation with Extended Euclidean Algorithm

Question

I'm a high school student writing a paper on RSA, and I'm doing an example with some very small prime numbers. I understand how the system works, but I can't for the life of me calculate the private key using the extended euclidean algorithm.

Here's what I have done so far:

• I have chosen the prime numbers p=37 and q=89 and calculated N=3293
• I have calculated (p-1)(q-1)=3168
• I have chosen a number e so that e and 3168 are relatively prime. I'm checking this with the standard euclidean algorithm, and that works very well. My e=25

Now I just have to calculate the private key d, which should satisfy ed=1 (mod 3168)

Using the Extended Euclidean Algorithm to find d such that de+tN=1 I get -887•25+7•3168=1. I throw the 7 away and get d=-887. Trying to decrypt a message, however, this doesn't work.

I know from my book that d should be 2281, and it works, but I can't figure out how they arrive at that number.

Can anyone help? I've tried solving this problem for the last 4 hours, and have looked for an answer everywhere. I'm doing the Extended Euclidean Algorithm by hand, but since the result works my calculations should be right.

Thanks in advance,

Mads