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.

Bibliography

1

Florentin Smarandache, A Generalization of Euler Theorem, Bulet. Univ. Brasov, Series C, Vol. XXIII, 7-12, 1981; online article in arXiv.

2

Florentin Smarandache, Collected Papers, Vol. I, 184-191 (in French), Tempus, Bucharest, 1996; online book.