Эйлера: если а сZ и м сN такие, что (a,m)=1 то a^(фи(м))≡1(мод м). Формылы для выч. фи(м): фи(1)=1, фи(р)=р-1Б если р-простое, фи(р^альфа)= р^альфа - p^(альфа-1). Напр: фи(1000)=2^3*5^3(1-1/2)(1-1/5)=400. Док-во: 
- прив. сис.выч.(а,м)=1, => ax1≡x1'(modm), ax2≡x2'(mod m), axфи(m)≡xфи(m)'(мод м). Перемножим все сравнения в системе. aфи(м)*x1*x2*xфи(м)≡x1'*x2'*x'фи(м) (mod m). -прив. сист.выч., т.к в ней каждый вычет вз прост с модулем (x1*x*2*xфи(м);m)=1. Поделим посл.сравнение на число, вз простое с модулем. aфи(м)≡1(mod m)
Ферма:Для любого простого р и любого а≥1 не делящегося на р справедливо сравнение a^(p-1)≡1(mod p). Теорема Ферма является частным случаем теоремы Эйлера. Док-во: ap-a=a(ap-1-1). Если (a,p)=1, то по т. эйлера след, что ap-1≡1(mod p), т.е ap-a≡р. Если (a,p)=p, то a≡p, т.е ap-a≡р
