АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Якщо к спільний дільник чисел a,b,(modm) то обидві частини і mod можна поділити на дане число к

Читайте также:
  1. B) Отрицательное число.
  2. I. Случайные величины с дискретным законом распределения (т.е. у случайных величин конечное или счетное число значений)
  3. I.Почему без бактерий и грибов жизнь на Земле была бы невозможна?
  4. II. Умножение матрицы на число
  5. III. ОСНОВНЫЕ АКСИОМЫ ЧИСЛА (ЧИСЛО КАК СУЖДЕНИЕ)
  6. III. Умножение вектора на число
  7. IV. ФУНКЦИЯ И СОСЕДНИЕ КАТЕГОРИИ (ЧИСЛО КАК СУЖДЕНИЕ, УМОЗАКЛЮЧЕНИЕ, ДОКАЗАТЕЛbСТВО И ВЫРАЖЕНИЕ)
  8. N – число измерений.
  9. N- число ступеней изменения концентраций
  10. Ni – число абонентских номеров для i- ой ТС.
  11. Аксиома ставшего числового бытия в арифметике.
  12. Аксиома ставшего числового бытия в геометрии.

Озн:Якщо з кожного класу лишків взяти по одному представнику, то одержана множина лишків називається повною системою лишків(ПСЛ). Числа класів називаються лишками. ПСННЛ={0,1,2,3,4,5,6}

Властивість: Теорема про ПСЛ: Якщо a,m взаємно прості НСД(a,m)=1 і b будь-яке ціле число,то якщо х пробігає ПСЛ, то ах+b також пробігає ПСЛ. Доведення: Нехай є ПСЛ за тоді покажемо, що ця множина чисел утворює повну систему лишків. Ця система містить m чисел: покажемо що числа цієї множини не порівнюються між собою за (modm).Припустимо від супротивного: так як а взаємно прості то а це суперечить умові теореми.А значить наше припущення вірне.Множина лишків,які належать різним класам і які взаємо прості з (modm)називають зведеною системою лишків(ЗСЛ).Як правило ЗСЛ ємножина найменших невід’ємних лишків.Очевидно,що ЗСЛ за (modm)містить -лишків, -функйія Ейлера.

Якщо a,m прості і х пробігає ЗСЛ,то і ах також пробігає ЗСЛ.НСД(a,m)=1.

Покажемо, що ці числа не порівнюються між собою за (modm).Припустимо, що

Це суперечить означенню ЗСЛ.

Теорема Ейлера:Якщо am взаємно прості. .

Доведення: Розглянути ЗСЛ(modm)={ }тоді згідно теореми про ЗСЛ множина також буде зведеною системою лишків. . Очевидно, що лишок з одним із лишків .

Тоді . Очевидно, що лишки попарно прості. А значить обидві частини останнього порівняння можна скоротити. .

Теорема Ферма:є частковим випадком теореми Ейлера,якщо m просте число;m=p;φ(p)=p-1.

.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |


При использовании материала, поставите ссылку на Студалл.Орг (0.006 сек.)