пользователей: 21258
предметов: 10464
вопросов: 177980
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Теоремы Эйлера и Ферма

Эйлера: если а сZ и м сN такие, что (a,m)=1 то a^(фи(м))≡1(мод м). Формылы для выч. фи(м): фи(1)=1, фи(р)=р-1Б если р-простое, фи(р^альфа)= р^альфа - p^(альфа-1). Напр: фи(1000)=2^3*5^3(1-1/2)(1-1/5)=400. Док-во:  x_1,...,x_{\varphi(m)} - прив. сис.выч.(а,м)=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≡р


11.01.2016; 20:27
хиты: 12
рейтинг:0
Точные науки
математика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь