# corollary of Euler-Fermat theorem

Corollary of Euler-Fermat theorem (F. Smarandache):
Let $a,m\in\mathbb{N}$, $m\neq 0$, and $\phi$ be the Euler totient function. Then:

 $a^{\phi(m_{s})+s}\equiv a^{s}\pmod{m}$

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}\neq 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}\neq 1$ go to the next step, otherwise stop;

$\ldots\ldots\ldots\ldots\ldots\ldots\ldots$

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}\neq 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 CorollaryOfEulerFermatTheorem 2013-03-22 14:23:14 2013-03-22 14:23:14 kamala (5486) kamala (5486) 9 kamala (5486) Result msc 11-00