let a, b, m, n be 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 Nat st S₁[k] holds
S₁[k + 1]

proof

let k be 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 12;
(a |^ (k + 1)) mod m = ((a |^ k) * a) mod m by NEWTON:6
.= ((l1 mod m) * (a mod m)) mod m by NAT_D:67
.= (l2 * b) mod m by A1, A3, NAT_D:67
.= (b |^ (k + 1)) mod m by NEWTON:6 ;
hence S₁[k + 1] ; :: thesis: verum

end;

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