# Is it possible to calculate $3^{-1}\equiv ?\pmod{10}$?

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?

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

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

-

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 ;-)

-

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

-
+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$).

-
Oops. Edited it. – JLA Jul 18 '13 at 6:08
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
@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.

-

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

-