# Can someone explain the following modular arithmetic? [duplicate]

$$7^{-1} \bmod 120 = 103$$

I would like to know how $$7^{-1} \bmod 120$$ results in $$103$$.

• What number when multiplied by $7$ results in a number which gives remainder $1$ when divided by $120$? – Rick Jul 10 '19 at 6:27
• The statement is that $-17\cdot 7=1\pmod{120}$. This is easy to verify as the left side is $-119=1-120$. – Lutz Lehmann Jul 10 '19 at 6:30
• It just means that $7\times103\equiv1\pmod{120}$. – Angina Seng Jul 10 '19 at 6:33
• long division and a little basic modular arithmetic... – user645636 Jul 11 '19 at 15:33

Using Carmichael Function, $$\lambda(120)=4$$

As $$(7,120)=1, 7^4\equiv1\pmod{120}$$

$$7^{-1}\equiv7^3\equiv343\equiv103$$

Like

Solving a Linear Congruence

$$\dfrac{120}7=17+\dfrac17$$

$$\implies120\cdot1-17\cdot7=1$$

$$\implies-17\cdot7\equiv1\pmod{120}$$

$$7^{-1}\equiv-17\equiv-17+120$$

Imagine a clock that has a large enough dial so that one can write numbers 0 to 119 (totally 120 numbers).

Now start at 0. Move clockwise jumping in steps of seven, so the first step will land in 7, 2nd step will land in 14, .... 10th step at 70, ... 15th step at 105, 18th step at 6 .....etc

Now your statement $$7^{-1}= 103 \pmod{120}$$ means the number 1 will be reached in 103rd step (when jumping in steps of 7 starting from 0).

Similarly $$37^{-1}=13\pmod{120}$$ means when jumping by 37 at a time starting from 0 one will reach 1 in the 13th step.

How exactly to calculate this is a different matter: it is by using extended Euclidean algorithm