corollary of Euler-Fermat theorem

Corollary of Euler-Fermat theorem (F. Smarandache):
Let a,m, m0, and ϕ be the Euler totient function. Then:


where s and ms depend on a and m, also s is one more than the number of steps in the algorithmMathworldPlanetmath, while ms is a divisorMathworldPlanetmathPlanetmathPlanetmath of m, and they are both obtained from the following integer algorithm:

Step (0):
calculate the gcd of a and m and denote it by d0;
therefore d0=(a,m), and also denote m0=m/d0;
if d01 go to the next step, otherwise stop;

Step (1):
calculate the gcd of d0 and m0 and denote it by d1;
therefore d1=(d0,m0), and also denote m1=m0/d1;
if d11 go to the next step, otherwise stop;

Step (s-1):
calculate the gcd of ds-2 and ms-2 and denote it by ds-1;
therefore ds-1=(ds-2,ms-2), and also denote ms-1=ms-2/ds-1;
if ds-11 go to the next step, otherwise stop;

Step (s):
calculate the gcd of ds-1 and ms-1 and denote it by ds;
therefore ds=(ds-1,ms-1), and also denote ms=ms-1/ds;
eventually one arrives at a gcd ds=1, stop the algorithm.

The algorithm ends when the gcd=1. Actually at each step the gcd decreases: from the maximum gcd=(a,m) at step (0) to the minimum gcd=1 at step (s). The algorithm is finite because the first gcd of (a,m) is finite and at each step one gets a smaller gcd.

For the particular case when (a,m)=1 one has s=0 (hence the algorithm finishes at step (0)) and ms=m, which is Euler-Fermat theorem.


  • 1 Florentin Smarandache, A Generalization of Euler Theorem, Bulet. Univ. Brasov, Series C, Vol. XXIII, 7-12, 1981; article in arXiv.
  • 2 Florentin Smarandache, Collected Papers, Vol. I, 184-191 (in French), Tempus, Bucharest, 1996; smarandache/CP1.pdfonline book.
Title corollary of Euler-Fermat theorem
Canonical name CorollaryOfEulerFermatTheorem
Date of creation 2013-03-22 14:23:14
Last modified on 2013-03-22 14:23:14
Owner kamala (5486)
Last modified by kamala (5486)
Numerical id 9
Author kamala (5486)
Entry type Result
Classification msc 11-00