EULER'S TOTIENT FUNCTION AND CONGRUENCE THEOREM
GENERALIZED BY SMARANDACHE
Let a, m be integers, m different from 0. Then:
phi(m ) + s
s s
a is congruent to a (mod m),
where phi(x) is Euler's Totient Function,
and s and m are obtained through the algorithm:
s
___
| a = a d ; (a , m ) = 1;
| 0 0 0 0
(0) |
| m = m d ; d different from 1;
| 0 0 0
---
___ 1 1
| d = d d ; (d , m ) = 1;
| 0 0 1 0 1
(1) |
| m = m d ; d different from 1;
| 0 1 1 1
---
....................................................
___ 1 1
| d = d d ; (d , m ) = 1;
| s-2 s-2 s-1 s-2 s-1
(s-1)|
| m = m d ; d different from 1;
| s-2 s-1 s-1 s-1
---
___ 1 1
| d = d d ; (d , m ) = 1;
| s-1 s-1 s s-1 s
(s) |
| m = m d ; d = 1.
| s-1 s s s
---
Therefore it is not necessary for a and m to be coprime.
25604
Example: 6 is congruent to ? (mod 105765).
It is not possible to use Fermat's or Euler's theorems,
but the Smarandache Congruence Theorem works:
d = (6, 105765) = 3
0
m = 105765/3 = 35255
0
i = 0
3 is different from 1
thus i = 0+1 = 1
d = (3, 35255) = 1
1
m = 35255/1 = 35255.
1
phi(35255)+1 1
Therefore 6 is congruent to 6 (mod 105765)
25604 4
whence 6 is congruent 6 (mod 105765).
References:
[1] Porubsky, Stefan, "On Smarandache's Form of the Individual Fermat-
Euler Theorem", , Vol. 8, No. 1-2-3,
Fall 1997, pp. 5-20, ISSN 1084-2810.
[2] Porubsky, Stefan, "On Smarandache's Form of the Individual Fermat-
Euler Theorem", , University of Craiova,
August 21-24, 1997, pp. 163-178, ISBN 1-879585-58-8.
[3] Smarandache, Florentin, "Une generalization de theoreme d'Euler"
(French), , Seria C, Vol. XXIII,
1981, pp. 7-12, reviewed in Mathematical Reviews: 84j:10006.
[4] Smarandache, Florentin, "Collected Papers", Vol. I, Ed. Tempus,
Bucharest, 1996, pp. 182-191.