let a, b, m be Nat; :: thesis: for n being Element of NAT st a mod m = b mod m holds
(a |^ n) mod m = (b |^ n) mod m
let n be Element of NAT ; :: thesis: ( a mod m = b mod m implies (a |^ n) mod m = (b |^ n) mod m )
defpred S₁[ Nat] means (a |^ $1) mod m = (b |^ $1) mod m;
assume A1: a mod m = b mod m ; :: thesis: (a |^ n) mod m = (b |^ n) mod m
A2: for k being Element of NAT st S₁[k] holds
S₁[k + 1]

proof

let k be Element of NAT ; :: thesis: ( S₁[k] implies S₁[k + 1] )
assume A3: S₁[k] ; :: thesis: S₁[k + 1]
reconsider l1 = a |^ k, l2 = b |^ k, a = a, b = b, m = m as Element of NAT by ORDINAL1:def 13;
(a |^ (k + 1)) mod m = ((a |^ k) * a) mod m by NEWTON:11
.= ((l1 mod m) * (a mod m)) mod m by EULER_2:11
.= (l2 * b) mod m by A1, A3, EULER_2:11
.= (b |^ (k + 1)) mod m by NEWTON:11 ;
hence S₁[k + 1] ; :: thesis: verum

end;

a |^ 0 = 1 by NEWTON:9;
then A4: S₁[ 0 ] by NEWTON:9;
for k being Element of NAT holds S₁[k] from NAT_1:sch 1(A4, A2);
hence (a |^ n) mod m = (b |^ n) mod m ; :: thesis: verum