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.

If I wanted to calculate $3^{-1}\equiv ?\pmod{10}$ would I first calcuate $3^1$ which is just $3\equiv 3\pmod{10}$ and then divide both sides by $3^2$ which would get $3^{-1}\equiv 3^{-1} mod{10}$ Then im not sure what to do next. My book states that $3^{-1}\equiv 7\pmod{10}$ which I don't know how they get?

share|improve this question
1  
Writing down things like $3\equiv3$ and $3^{-1}\equiv3^{-1}$ accomplish nothing, and you can certainly get $a\equiv a$ without having to do anything like division. For small enough numbers to find $x^{-1}$ mod $n$ (where $x,n$ are necessarily coprime) it suffices to check the numbers $1+nm$ for being divisible by $x$ until you find such a case, in which case $x^{-1}$ is congruent to $\frac{1+nm}{x}$. So for example here, you would check $1,11,21,31,\cdots$ for divisibility by $3$. Clearly $21$ is divisible by $3$, so $3\cdot7\equiv1$ mod $10$, so $3^{-1}\equiv7$ mod $10$. –  anon Jul 18 '13 at 6:07
2  
Another thing you could notice is that $3^{-1}\equiv 3/3^2\equiv 3/(-1)\equiv-3\equiv7$. Another trick is the totient theorem mentioned by lab: since $x^{\varphi(n)}\equiv1$, we have $x^{\varphi(n)-1}\equiv x^{-1}$. Finally the standard algorithmic approach is known as the extended Euclidean algorithm. –  anon Jul 18 '13 at 6:11
    
Thanks just by using the Euler totient theorem makes it a lot easier –  user60887 Jul 18 '13 at 6:31
    
I even forgot that you can use the symmetric property of congruences as well. –  user60887 Jul 19 '13 at 19:23

6 Answers 6

As $\phi(10)=4$ and $(3,10)=1$ using Euler's Totient Theorem $3^4\equiv1\pmod {10}$

Also, we can directly observe $3^4=81\equiv1\pmod{10}$

$\implies 3^{-1}\equiv3^3\equiv7\pmod{10}$

share|improve this answer

A number $x^{-1}$ is one such that $x \cdot x^{-1} = 1$ (here $\mod 10$). In this case it is easy, because there is only 10 possibilities: $0,1,2,3,4,5,6,7,8,9$, with product being $0,3,6,9,2,5,8,1,4,7$ respectively. That means there exists, and there exists only one number such that $$x \cdot x^{-1} = 1 \mod 10.$$ There are other solutions like $17, 27, 37$ but those are $\geq 10$ or $< 0$ (curiously $-3$ is such a number, that is $3\cdot -3 = -9 = 1 \mod 10$).

The general approach can be done via the Euclidean algorithm, which for any numbers $a,b$ lets you find $x,y$ such that

$$a x + b y = \gcd(a,b).$$

Happily $3$ and $10$ are coprime, that is $\gcd(3,10) = 1$, which allows as to run the algorithm and get $3 \cdot (-3) + 10 \cdot (1) = 1$, giving us $x = -3$, now it is enough to move $x$ to appropriate interval, that is $x+10k$ such that $0 \leq x+10k < 10$, and that gives us $7$.

I hope this helps ;-)

share|improve this answer

You need to find $x$ such that

$3x\equiv1\equiv 21\pmod {10}\implies x\equiv 7\pmod{10}\tag{as $\gcd(3,10)=1$}$

share|improve this answer
    
+1 thanks for noting me that bad typo. :-) –  Babak S. Jul 18 '13 at 13:32

In this case it's easiest to just look at the numbers: The options for the inverse are $4$ and up, and $3 \times 4=12$, $3\times 5=15$, $3\times 6=18$, $3\times 7=21$. Hence the inverse is $7$ since $21=1$ (mod $10$).

share|improve this answer
    
Oops. Edited it. –  JLA Jul 18 '13 at 6:08
1  
if $a\cdot b\equiv1\pmod m, (a,m)=(b,m)=1$ So, we just need to check multipliers co-prime to $10$ –  lab bhattacharjee Jul 18 '13 at 6:12
    
Or simply see that $3 \times 3 = 9 \equiv -1$, hence $3^{-1} \equiv -3 \equiv 7$. –  Jean-Claude Arbaut Jul 18 '13 at 6:15
    
Why 4 and up? the inverse for 7 is 3, 3 < 7. –  dtldarek Jul 18 '13 at 6:20
1  
@Tomas Yeah, well, I know, it's only that it seemed that the OP needs a very basic approach, and a trick that lets you save 3 seconds isn't worth mentioning (that is, it complicates more than it simplifies). –  dtldarek Jul 18 '13 at 8:53

You can generally calculate the value of $1/x \pmod{10}$, by way of reverse division. This can be applied to numbers of any size. For example, find the number, which when multiplied by $183$, is $1$ modulo $1000$.

            8 4 7 
            -----                                   8 4 7
      183)  0 0 1                                   1 8 3
            2 8 1  (7   7*183 = 1281          ===========
            -----                                 2 5 4 1       
            7 2 0                               6 7 7 6
            3 2   (40   4*183 = 732             8 4 7
           ------                            -------------
            4                                 1 5 5 0 0 1
            4    (800   8*183 = 1464
           --
            0    (847

For small numbers, like 3 or 7, one can do 'short division', so 0 0 0 1 divide by 3 gives 6 6 6 7.

share|improve this answer

Hint: Notice that $10-3 \times 3 =1$.

share|improve this answer

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.