linguistic:paraphrasing
Euler's theorem

This states that if a and n are relatively prime then

The special case where n is prime is known as Fermat's little theorem.

This follows from Lagrange's theorem and the fact that φ (n) is the order of the multiplicative group of integers modulo n.

The RSA cryptosystem is based on this theorem: it implies that the inverse of the function a ↦ a mod n, where e is the (public) encryption exponent, is the function b ↦ b mod n, where d, the (private) decryption exponent, is the multiplicative inverse of e modulo φ (n). The difficulty of computing φ (n) without knowing the factorization of n is thus the difficulty of computing d: this is known as the RSA problem which can be solved by factoring n. The owner of the private key knows the factorization, since an RSA private key is constructed by choosing n as the product of two (randomly chosen) large primes p and q. Only n is publicly disclosed, and given the difficulty to factor large numbers we have the guarantee that no one else knows the factorization.