Euler’s theory (18TH CENTURY)

Devised by Swiss mathematician Leonhard Euler (1707-1783), Euler’s theory is a theory of distribution based on marginal productivity.

Euler showed that under constant returns to scale, if each factor of production is paid the value of its marginal product, total output (income) will be completely exhausted.

Also see: adding-up problem, marginal productivity theory of distribution, returns to scale

Source:
L C Young, Lectures on the Calculus of Variations and Optimal Control Theory (Philadelphia, 1969)

In number theory, Euler’s theorem (also known as the Fermat–Euler theorem or Euler’s totient theorem) states that if n and a are coprime positive integers, then a raised to the power of the totient of n is congruent to one, modulo n, or:

{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}

where {\displaystyle \varphi (n)} is Euler’s totient function. In 1736, Leonhard Euler published his proof of Fermat’s little theorem,^[1] which Fermat had presented without proof. Subsequently, Euler presented other proofs of the theorem, culminating with “Euler’s theorem” in his paper of 1763, in which he attempted to find the smallest exponent for which Fermat’s little theorem was always true.^[2]

The converse of Euler’s theorem is also true: if the above congruence is true, then {\displaystyle a} and {\displaystyle n} must be coprime.

The theorem is a generalization of Fermat’s little theorem, and is further generalized by Carmichael’s theorem.

The theorem may be used to easily reduce large powers modulo {\displaystyle n}. For example, consider finding the ones place decimal digit of {\displaystyle 7^{222}}, i.e. {\displaystyle 7^{222}{\pmod {10}}}. The integers 7 and 10 are coprime, and {\displaystyle \varphi (10)=4}. So Euler’s theorem yields {\displaystyle 7^{4}\equiv 1{\pmod {10}}}, and we get {\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}}.

In general, when reducing a power of {\displaystyle a} modulo {\displaystyle n} (where {\displaystyle a} and {\displaystyle n} are coprime), one needs to work modulo {\displaystyle \varphi (n)} in the exponent of {\displaystyle a}:

if {\displaystyle x\equiv y{\pmod {\varphi (n)}}}, then {\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}.

Euler’s theorem underlies RSA cryptosystem, which is widely used in Internet communications. In this cryptosystem, Euler’s theorem is used with n being a product of two large prime numbers, and the security of the system is based on the difficulty of factoring such an integer.