# Power Reduction in Congruences

Suppose you have integers a,b that are relatively prime to m such that

then

- 15 August, 2012 -
- Article, Math Problems -
- Tags : 104 problems, number theory, titu
- 0 Comments

We first prove a useful lemma in working with algebraic manipulations in modular arithmetic.

### 1. Lemma:

Here, we take the traditional definition that .

### 2. Show that

By construction of the , we know that . It follow that

The last two lines of the above gives another congruence expression:

Suppose that as must be positive. Because are both relatively prime to , then by the above lemma, we know that

Likewise, we can divide out from both sides

this gives us our final congruence equivalence

Because, , the above simplifies down to .

#### Alternatively

The same logic above can be used to justify that , therefore, you can also show inductively, on the steps of the euclidean algorithm, that it preserves the properties of congruence mod m.