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(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.

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