Working out modulo of negative powers

Question

Say we have the following: $3^{-1}\bmod 7$, how do we calculate this without a calculator? I was gonna do $3^1 \bmod 7 = 3$.

Answer 1

From Euclidean division $7=3\times2+1,$ we can see that $1=7+3\times-2$.

Modulo $7$, this reads $1\equiv3\times-2,$ or $1\equiv3\times5$;

this indicates that $-2$ or $5$ is the inverse of $3$ modulo $7$.

Answer 2

Even in modular arithmetic, it is true that $3^{-1} \cdot 3^1 = 1$

So you just need to find a value $x$ such that $3 \cdot x = 1$. Fortunately, you only have 7 options to check in mod 7. $x$ could equal $0,1,2,3,4,5$ or $6$

Answer 3

If you weren't a beginner, we could do it as follows:

$${(7-1)\over 3}=2\therefore 3\cdot(7-2)\equiv 1\bmod 7$$ This reads as, subtracting 1 from 7 and dividing by 3 gives you 2. Therefore, 3 times the number created from subtracting 2 from 7 is congruent to 1 mod 7.

It's pretty much a mirroring argument of: 2 times 3 is 6, therefore (-2) times 3 is (-6). (-6)+7=1 is the least positive equivalent mod 7 .