Question

someone check this proof for me?

Answer 1

proof by induction that \[a^n \mod b = (a \mod b)^n \mod b\]

let

\[A = \left\{ n | \text{ } a^n \mod b = (a \mod b)^n \mod b \right\}\]

consider the case n = 1

\[a^1 \mod b = (a \mod b)^1 \mod b \]

therefore \[1 \in A\]

now assume \[k \in A \]
for some k
\[a^{k+1} \mod b = (a \mod b)(a^{k} \mod b) \mod b \]\[= (a \mod b)(a \mod b)^k \mod b \]\[= (a \mod b)^{k+1} \mod b \]

now we have

\[1 \in A \text{ and } k \in A \implies k+1 \in A\]

therefore the natural numbers is a subset of A, and the property holds for all natural numbers

Answer 2

also i'd like advice on improving how i wrote the proof

Answer 3

this is beautiful...i would like to see an example about this

Answer 4

thanks, i saw this used in a book without proof so i decided to provide my own

\[2^{60} \mod 61 = (2^6 \mod 61)^{10} \mod 61\]\[ = ( 64 \mod 61)^{10} \mod 61 \]\[= 3^{10} \mod 61\]\[= (3^5 \mod 61)^2 \mod 61\]\[=(243 \mod 61)^2 \mod 61\]\[= 60^2 \mod 61\]\[=1\]

Answer 5

In fact a deeper approach is tp prove that resicdue of division form a group (cyclical group) and the theorem in fact follows. Also the Fermat's little th. is a consequence

Answer 6

ah, i haven't done any group theory before. i plan to, looks very interesting

Answer 7

This is not the full-on "group theory" it is the simplest and most transparent case of a group (and a ring btw) . So it does not the real "learn group theory" - just the first of the first

Answer 8

ill take a look at some point today

Answer 9

Cyclic(-al) group