Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
A related problem. –  Mhenni Benghorbal Jun 26 '13 at 2:34

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.