# corollary of Euler-Fermat theorem

Corollary of Euler-Fermat theorem (F. Smarandache):

Let $a,m\in \mathbb{N}$, $m\ne 0$, and $\varphi $ be the Euler totient function. Then:

$${a}^{\varphi ({m}_{s})+s}\equiv {a}^{s}\phantom{\rule{veryverythickmathspace}{0ex}}(modm)$$ |

where $s$ and ${m}_{s}$ depend on $a$ and $m$, also $s$ is one more than the number of steps in the algorithm^{}, while ${m}_{s}$ is a divisor^{} 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 ${d}_{0}$;

therefore ${d}_{0}=(a,m)$, and also denote ${m}_{0}=m/{d}_{0}$;

if ${d}_{0}\ne 1$ go to the next step, otherwise stop;

Step (1):

calculate the gcd of ${d}_{0}$ and ${m}_{0}$ and denote it by ${d}_{1}$;

therefore ${d}_{1}=({d}_{0},{m}_{0})$, and also denote ${m}_{1}={m}_{0}/{d}_{1}$;

if ${d}_{1}\ne 1$ go to the next step, otherwise stop;

$\mathrm{\dots}\mathrm{\dots}\mathrm{\dots}\mathrm{\dots}\mathrm{\dots}\mathrm{\dots}\mathrm{\dots}$

Step (s-1):

calculate the gcd of ${d}_{s-2}$ and ${m}_{s-2}$ and denote it by ${d}_{s-1}$;

therefore ${d}_{s-1}=({d}_{s-2},{m}_{s-2})$, and also denote ${m}_{s-1}={m}_{s-2}/{d}_{s-1}$;

if ${d}_{s-1}\ne 1$ go to the next step, otherwise stop;

Step (s):

calculate the gcd of ${d}_{s-1}$ and ${m}_{s-1}$ and denote it by ${d}_{s}$;

therefore ${d}_{s}=({d}_{s-1},{m}_{s-1})$, and also denote ${m}_{s}={m}_{s-1}/{d}_{s}$;

eventually one arrives at a gcd ${d}_{s}=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 ${m}_{s}=m$, which is Euler-Fermat theorem.

## References

- 1 Florentin Smarandache, A Generalization of Euler Theorem, Bulet. Univ. Brasov, Series C, Vol. XXIII, 7-12, 1981; http://xxx.lanl.gov/pdf/math.GM/0610607online article in arXiv.
- 2 Florentin Smarandache, Collected Papers, Vol. I, 184-191 (in French), Tempus, Bucharest, 1996; http://www.gallup.unm.edu/ 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 |