Congruence classes: Find the inverse I have the following problem:

If $ [3640]$ is invertible in $\mathbb {Z}_{7297}$ then determine its inverse.

Okay. The first thing I thought was:
$$3640x\equiv 1 \pmod{7297}$$
But isn't there any easier way? 
Any hint, much appreciated.
 A: We use the Euclidean Algorithm. Note that
$$7297=(2)(3640)+17.\tag{A}$$
$$3640=(214)(17)+2.\tag{B}$$
$$17=(8)(2)+1.\tag{C}$$
Now go backwards. We have from (C) that
$$1=17-(8)(2).\tag{1}$$
But from (B) we have $2=3640-(214)(17)$.
Substituting for the $2$ in Equation (1), we get
$$1=17-8[3640 -(214)(17)]=(-8)(3640)+(1713)(17). \tag{2}$$
Now from (A) we have  $17=7297-(2)(3640)$. Substitute for the $17$ 
in Equation (2). We get 
$$1=(-8)(3640)+(1713)[7297-(2)(3640)].$$
Thus $1$ is equal to $(-3434)(3640)$ plus a multiple of $7297$. 
So one answer is $-3434$. If you want a positive answer, add $7297$. We get $3863$.
Admittedly, a little unpleasant, but fully mechanical. There are nicer ways to implement this Extended Euclidean Algorithm, but for smallish numbers like these, back substitution is not too bad.
A: Note that $\rm ax\equiv 1 ~mod~b\iff ax+by=1\iff by\equiv 1~mod~a$ (with appropriate quantifiers).
Two good methods to compute $\rm x,y$ given coprime $\rm a,b$:


*

*The standard: Extended Euclidean Algorithm

*What Dubuque calls Gauss' algorithm:
$$\rm mod~7297:\quad \frac{1}{3640}\equiv\frac{2}{7280}\equiv-\frac{2}{17}\equiv-\frac{2\cdot 429}{7293}\equiv\frac{429}{2}\equiv429\cdot\frac{7298}{2}\equiv3836.$$
At each stage the idea is to multiply numerator and denominator by whatever minimizes the difference $\rm |modulus-multiplier\cdot denominator|$, then reduce and cancel any shared factors; for example with $\rm 2/17$ we see that $\rm 7297/17$ is closest to the integer $429$, so we multiply by that, and similarly we factor out negatives where possible.
A: Hint: $(-3434) \cdot 3640+ 1713 \cdot7297 = 1$
