let n, p be Nat; :: thesis: ( p is prime & n,p are_relative_prime implies (n |^ (p -' 1)) mod p = 1 )
assume A1: ( p is prime & n,p are_relative_prime ) ; :: thesis: (n |^ (p -' 1)) mod p = 1
then A2: p > 1 by INT_2:def 5;
A3: p <> 0 by A1, INT_2:def 5;
A4: n <> 0

proof

assume n = 0 ; :: thesis: contradiction
then n gcd p = p by NEWTON:65;
then n gcd p > 1 by A1, INT_2:def 5;
hence contradiction by A1, INT_2:def 4; :: thesis: verum

end;

then (n |^ p) mod p = n mod p by A1, EULER_2:34;
then A5: ((n |^ (p -' 1)) * n) mod p = n mod p by A3, A4, Th27;
n |^ (p -' 1) <> 0 by A4, PREPOWER:12;
hence (n |^ (p -' 1)) mod p = 1 by A1, A2, A4, A5, EULER_2:27; :: thesis: verum