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

-
7297 is a prime number. What do I do? @PeterTamaroff – HipsterMathematician Jun 26 '13 at 0:46
@PeterTamaroff you so silly.Thanks for your help, Pedro Nicolás. – HipsterMathematician Jun 26 '13 at 0:52
3863 may be the answer. – eccstartup Jun 26 '13 at 1:01
@ThomasAndrews You're right. – Pedro Tamaroff Jun 26 '13 at 1:11
– Mhenni Benghorbal Jun 26 '13 at 2:34

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.

-
There is a stranded dollar sign in the answer. – Pedro Tamaroff Jun 26 '13 at 1:02
@PeterTamaroff: Thank you, I think it is gone now. – André Nicolas Jun 26 '13 at 1:09
Thank you @AndréNicolas . – HipsterMathematician Jun 26 '13 at 1:19
You are welcome. It is quite standard to put such a question, with not too bad numbers, on a test or exam, with instruction that the Euclidean Algorithm must be used. – André Nicolas Jun 26 '13 at 1:23

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$:

1. The standard: Extended Euclidean Algorithm

2. What Dubuque called the "Gauss method":

$$\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.

-
Bill's method is quite awesome. – Pedro Tamaroff Jun 26 '13 at 1:12
Thanks, @anon . – HipsterMathematician Jun 26 '13 at 1:20

Hint: $(-3434) \cdot 3640+ 1713 \cdot7297 = 1$

-
Great. How did you find the numbers? – Pedro Tamaroff Jun 26 '13 at 0:57
Tedious GCD computation. ${}{}{}$ – copper.hat Jun 26 '13 at 1:02