Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

4 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.