Euler's theorem is a generalization of Fermat's little theorem and states that

 a^{\\varphi (m)} = 1 \\;\\; in \\;\\; Z_{m}

where \\varphi(m) is Euler's function and gcd(a,\\; m) = 1.

Euler's function

Euler's function \\varphi(n), where n \\gt 2, is defined as number of integers less than n, which are relatively prime to n (i.e. their greatest common divisor is equal to 1). \\varphi(1) is defined as 1.

Computing Euler's function

To compute Euler's function of n, we factorize n to its prime factors p_{1},\\; p_{2}, \\cdots ,\\; p_{r} and plug them into the following formula:


\\varphi (p_{1}^{n_{1}} \\cdot p_{2}^{n_{2}} \\cdots p_{r}^{n_{r}}) = p_{1}^{n_{1}} \\cdot (1 - {1 \\over p_{1}}) \\cdot p_{2}^{n_{2}} \\cdot (1 - {1 \\over p_{2}}) \\; \\cdots \\; p_{r}^{n_{r}} \\cdot (1 - {1 \\over p_{r}}) =

= n \\cdot (1 - {1 \\over p_{1}}) \\cdot (1 - {1 \\over p_{2}}) \\; \\cdots \\; (1 - {1 \\over p_{r}})

Proof of Euler's theorem

For each number greater than 0 and less or equal to m - 1, which is relatively prime to m and has an inverse in Z_{m}, there exist according to Euler's function exactly \\varphi(m) invertible elements. Let's denote them as b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{n}.

For every two elements b_{i} and b_{j}, where i and j are integers from set \\{0,\\; 1,\\; 2, \\cdots,\\; \\varphi (m)\\}, it holds that:

 b_{i} \\cdot a \\neq b_{j} \\cdot a \\;\\; in \\;\\; Z_{m}

because b_{i}, b_{j} and a are defined as numbers relatively prime to n.

Now suppose we have two following sequences:

b_{1} \\cdot a,\\; b_{2} \\cdot a,\\; b_{3} \\cdot a, \\cdots ,\\; b_{\\varphi (n)} \\cdot a
b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{\\varphi (n)}

The sequences contain identical numbers (regardless their order). So let's factor out a from the first sequence:


 a^{\\varphi (n)} \\cdot (b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{\\varphi (n)}) = b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{\\varphi(n)} \\;\\; in \\;\\; Z_{m}

Finally we can cancel out the whole second sequence and we get the desired expression:


a^{\\varphi (n)} = 1 \\;\\; in \\;\\; Z_{m}

Example

Calculate 7^{3822} in Z_{15}.

gcd(7, 15) = 1
15 = 5 \\cdot 3
\\varphi (15) = 15 \\cdot (1- {1 \\over 5}) \\cdot(1- {1 \\over 3}) = 8
{{3822} \\over {8}} = 477 \\; (residue \\; 6)
 7^{3822} = (7^{8})^{477} \\cdot 7^{6} = 1^{477} \\cdot 7^{6} = 1 \\cdot 7^{2} \\cdot 7^{2} \\cdot 7^{2} =  49 \\cdot 49 \\cdot 49 =
 = 4 \\cdot 4 \\cdot 4 = 16 \\cdot 4 = 1 \\cdot 4 = 4 \\;\\; in \\;\\; Z_{15}

Sources

  • VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 193 p.







       
 

Place for your banner

Here is the position ready for our customer's banners.