# modular arithmetic (number theory)

Assume that $$7^{64} = 1 \mod 120.$$

I am trying to find $$7^{62} \mod 120.$$

In my maths text, I was told that: \begin{align} 7^{62} & = 7^{64} \cdot 7^{-2} \\ & = 7^{-2} \quad \\ &= 49^{-1} \quad \, \, \mod 120 \end{align} I do not understand why $7^{64} \cdot 7^{-2}$ can be reduced to just $7^{-2}$. Can anyone explain to me?

-
I think some of the posted answers are more complicated than what is needed. I've added a really simple one. –  Michael Hardy Feb 17 '13 at 23:17
$7^{64}\cdot 7^{-2}=1 \cdot 7^{-2}$. –  N. S. Feb 17 '13 at 23:48

$7^{64} \equiv 1 \mod 120$. Thus, $7^{64} \times 7^{-2} \equiv 1\times7^{-2} \equiv 7^{-2} \mod 120$. This is a basic property of modolar arithmetic.

-

If $a\equiv b\bmod m$, then $ca\equiv cb\bmod m$ for any integer $c$. Thus, supposing that $$7^{62}\equiv x\bmod 120,$$ we have that $$7^{64}=7^2\cdot 7^{62}\equiv 7^2\cdot x\bmod 120,$$ and since you're told that $$7^{64}\equiv 1\bmod 120,$$ you have that $$1\equiv 7^2\cdot x\bmod 120.$$ This is the sense in which $$7^{62}\equiv x\equiv 7^{-2}\bmod 120.$$

-

It's just scaling an equality (congruence)

$\rm\quad \begin{array}{rl}\rm a \times (b\equiv c)\!\!\! &\to&\rm ab\equiv ac\\ \\ 7^{-2}\! \times (7^{64}\!\equiv 1)\!\!\! &\to& 7^{62}\equiv 7^{-2}\end{array}$

Remark $\$ Congruences $\rm\:a\color{#C00}{\equiv} b\:$ behave similar to equalities $\rm\:a\color{#C00}= b\:$ in that they can be added, and multiplied. Scaling is a special case of multiplication, i.e. above is the product of $\rm\:a \equiv a\:$ by $\rm\:b\equiv c.\:$ When working with congruences it is essential to conceive them as generalized equalities so that you can transfer all of your well-honed equational arithmetical skills to congruence arithmetic.

-

Multiply by $7$ at each step and reduce modulo $120$: $$1 \mapsto 7\mapsto 49 \mapsto 103\mapsto1 \mapsto 7\mapsto 49 \mapsto 103\mapsto1\mapsto\cdots\cdots$$ As soon as you see the pattern, you'll know how to do the problem.

-