Congruence is compatible with powers

Builds on Congruence modulo n Congruence is compatible with multiplication

Statement

Let $n$ be a positive integer, let $a$ and $b$ be integers, and let $k$ be a natural number. If $a \equiv b \pmod n$ , then $a^k \equiv b^k \pmod n$ .

Remarks

The proof is an induction on $k$ with compatibility with multiplication. The exponent cannot be reduced modulo $n$ in general. For example, $2^5 = 32 \equiv 2 \pmod 3$ , but $2^{5 \bmod 3} = 2^2 \equiv 1 \pmod 3$ . Euler's theorem tells when one can reduce the exponent, and by which modulus.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Congruence modulo n definition
Congruence is compatible with multiplication statement
Congruence is compatible with powers statement

Where this leads

3 pages build on this one.

Tag	`0J5VGJYYC3`
URI	`m2://0J5VGJYYC3`
Kind	statement, corollary
Writing	W0 stub
MSC	11A07
Status	This copy of the site has no build data. Run `m2 status 0J5VGJYYC3`.
Uses	Congruence modulo n, Congruence is compatible with multiplication

Congruence is compatible with powers

Statement

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by