Euler Theorem Generalized

EULER'S TOTIENT FUNCTION AND CONGRUENCE THEOREM GENERALIZED BY SMARANDACHE

Let a, m be integers, m different from 0. phi(m ) + s s

Then:

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

___ | | (0) | | |

---

a = a d 0 0

;

m = m d 0 0

;

___ | | (1) | | |

1 = d d 0 0 1 0

---

d

different from 1; 0

d m

(a , m ) = 1; 0 0

= m d 1 1

;

1 (d , m ) = 1; 0 1

;

d

different from 1; 1

.................................................... ___ | | (s-1)| | |

1 d

= d

m

= m

s-2

___ (s)

| | | | |

(d

, m

s-2

;

= d

m

= m d s s

s-1

) = 1;

s-1

d

different from 1; s-1

1 d

s-1

---

;

d s-1 s-1

s-2

---

1

d s-2 s-1

1

d s-1 s

; ;

(d

, m ) = 1; s

s-1

d

= 1. s

Therefore it is not necessary for a and m to be coprime. Example:

25604 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

m

= 105765/3 = 35255

0 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

Therefore 6

1

is congruent to 6

25604 whence 6

(mod 105765)

4 is congruent 6

(mod 105765).

References: [1] Porubsky, Stefan, "On Smarandache's Form of the Individual FermatEuler Theorem", <Smarandache Notions Journal>, Vol. 8, No. 1-2-3, Fall 1997, pp. 5-20, ISSN 1084-2810. [2] Porubsky, Stefan, "On Smarandache's Form of the Individual FermatEuler 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), <Buletinul Universitatii Brasov>, 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.