Euler Theorem. (1)

     Let j(n) be the quantity of numbers less than n and co-prime with it. Then for any a, co-prime with n, the number a^j(n)-1 is divisible by n.

     Proof. Let c₁, c₂, ... , c_j(n) be numbers less than n and co-prime with it. Let C denote their product. Let us consider numbers ac₁, ac₂, ... , ac_j(n). As a is co-prime with n, these numbers are also co-prime with n, at the same time they give different remainders when divided into n (is proved analogously to the small Fermat theorem). Consequently, when divided into n, the product of these numbers a^j(n)C gives the same remainder, as C. Then the difference a^j(n)C - C = C(a^j(n)-1) is divisible by n . As C is co-prime with n, it follows from the corollary Gaus theorem that a^j(n)-1 is divisible by n, what was to be proved.