1

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?

user60887
  • 2,935
  • 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 06: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 06:11
  • Thanks just by using the Euler totient theorem makes it a lot easier – user60887 Jul 18 '13 at 06:31
  • I even forgot that you can use the symmetric property of congruences as well. – user60887 Jul 19 '13 at 19:23

6 Answers6

5

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

lab bhattacharjee
  • 274,582
3

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

dtldarek
  • 37,381
1

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

Aang
  • 14,672
0

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

JLA
  • 6,442
  • 2
  • 24
  • 40
0

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.

wendy.krieger
  • 6,856
0

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

Seirios
  • 33,157