Определението и свойствата на остатъци
Обобщение на теорията
Прилагането на теоремата на делене с остатък може да бъде набор от цели числа, разделени в няколко класа. Помислете за пример. Нека m = 6. Тогава ние имаме шест класове дял на набора от цели числа по модул 6:
където R означава остатъка след разделяне на цяло число 6.
Припомнете теоремата на разделяне с остатък:
Теорема. Разделете броя от номер. , с остатъка, така че да се намери чифт числа р и г. такива, че са изпълнени следните условия :.
Лесно е да се докаже, че за всеки един числа и разделяне с остатък е възможно и броя на р и г са еднозначно определени. В този пример, цялостна система от неотрицателна поне има много удръжки; цялостна система от най-малко положително остатъкът - комплект; цялостна система от най-слабо удръжки абсолютна стойност - да; Горната приспадане система - толкова, колкото; фактор комплект
Метод за извършване на аритметични операции върху данните число на базата на прости разпоредби на теорията на числата. Идеята на този метод е, че цели числа се представят в една от nepozitsionnyh системи - в остатъчна система класове. А именно, вместо на операциите на числа работи с остатъци от разделянето на тези номера за предварително избрани прости числа - модули.
В повечето случаи, номерът се избира от множество прости числа.
Тъй като в пръстена от числа е теорема на разделяне с остатък, R. Д. Когато. Z. на пръстен, по дефиниция, е Euclidean.
По този начин, като цифрите може да бъде избран, като се раздели броя на остатъци в пи съответно.
приспадане система позволява аритметични операции върху ограничен набор от числа, няма да отидат извън нейните граници. Цялостна система на остатъци по модул N # 8213; всеки набор от п двойки неподходящ модул N числа. Обикновено като цялостна система от остатъци по модул н идват от най-малките остатъци неотрицателни
Числата се наричат също приспадане за modulyum. NeotritsatelnyeVYChETy а = R (когато р = 0), който взема стойности в интервала [0, 1. m - 1]. образуват цялостна система от остатъци най modulyum.
Например, когато М = 5 малко класове остатъци образуват
г = 0, 1, 2, 3, 4, а = -2, -1, 0, 1, 2. Двете групи от номера, дадени форма цялостна система остатък модул 5 а.
На остатъчни класове. елементи, които са взаимно прости с модул М
наречен намалена. функция на Ойлер определя колко приспадане от цялата система на остатъци modulyum поне относително прости за м. В един прост, трябва m = р = р-1.
Определение. Максимална набор от двоични числа м неподходящ модул сравнително премиер до м. Това се нарича понижено система на остатъци по модул m. Всеки от по-горе система на остатъци по модул m съдържа елементи, които - функция Ойлер.
Определение. Всеки брой на клас Je м равностойност свиква приспадане ия модул m. Комплектът на приспадане взети по един от всяка еквивалентност клас Je m. Той нарича пълно приспадане система модул m (пълно приспадане е система, така че всички номера м парчета). Директно се остатъци когато разделен от m е поне неотрицателна остатък на S и, разбира се, да образуват една цялостна система на приспадане и модул m. Приспадане R се нарича най-ниската абсолютна, ако ïRï най-малкия сред модули ите приспадане на този клас.
Пример. Проверка дали под формата на 13, 8-3, 10, 35, 60, пълна с остатъци по модул m = 6 система.
Решение. Чрез определянето на образуват цялостна система на остатъци по модул m. ако точно м и те са по двойки несравним в modulyum.
Двойки несравним може да се провери чрез замяна на всеки номер е най-малкият неотрицателна, мрежата; Ако не е повторение, то тогава е цялостна система от остатъци.
Ние прилага теоремата на разделяне с остатък: а = MQ + R.
13 6 = 2 + 1-ви януари, 13 (мод 6); 8 = 1 + 6 2 8 2 (мод 6);
-3 = 6 (1) 3 -3 + 3 (мод 6); 10 = 6 1 + 4 10 4 (мод 6);
35 = 5 + 6 35 5 5 (мод 6); 60 = 10 + 6 0 60 0 (мод 6).
Получени номера на последователност 1, 2, 3, 4, 5, 0, 6 са точно повторение и имат взаимно несравним. Това означава, че те образуват цялостна система на остатъци по модул m = 6.
Пример. Замяна на най-малката в абсолютна стойност, както и най-малкото положително остатъкът по модул 16 185.
Решение. Ние прилагаме теоремата на делене с остатък:
185 = 16 11 ± 9 185 9 (мод 16).
Пример. Проверка дали броят на форма (13, -13, 29, -9) намалената остатък система модул т = 10.
Решение: Всяко Горната система на остатъци по модул m съдържа елементи, които - Ойлер функция. В този случай к = 4, тъй като сред естествени числа само 1, 3, 7, 9 взаимно прости с 10, и не я надвишава. Това означава, че е възможно, че тези четири числа образуват желаната система. Ние проверяваме тези номера на своя двойки несравним:
13 = 10 1 + 3; 13 март (мод 10); - 13 10 = (- 2) + 7; -13 7 (мод 10);
29 = 10 2 + 9; 29 септември (мод 10); - 9 10 = (- 1) + 1; - Септември 1 (мод 10).
Всичко брой двойки несравним, никой от тях не се повтаря, има точно 4 и те не надвишават модула. Следователно, те формират понижено система остатък.
Пример. Проверява дали броят на форма (-349, -193, 231, 401) на понижено остатък система модул т = 12.
Решение: В този случай к = 4, тъй като сред естествени числа само 1, 3, 7, 9 взаимно прости с 10, и не я надвишава. Това означава, че е възможно, че тези четири числа образуват желаната система. Ние проверяваме тези номера на своя двойки несравним:
-349 = 12 (-30) + 11; -349 11 (мод 12);
- 193 = 12 (-17) + 11; -193 11 (мод 12);
231 = 12 19 + 3; 231 3 (мод 12);
401 = 12 33 + 5; 401 5 (мод 12).
Сред цифрите са повторение, ние имаме две сравними числа -349 и -193. Следователно, броят не формират понижено система остатък.
Създаване 1. Промяна на броя и най-малката в абсолютна стойност, както и най-малкото положително остатък по модул м.
Вариант 1. = 185, m = 12; Вариант 2. = 84, m = 9;
Вариант 3. = 180, m = 10; Аспект 4. = 82, m = 9;
Аспект 5. = 85, m = 11; Аспект 6. = 84, m = 8;
Аспект 7. = 103, m = 87; Аспект 8. = 84, m = 16;
Аспект 9. = 15, m = 10; Аспект 10. = 81, m = 9;
Аспект 11. = 85, m = 15; Аспект 12. а = 74, m = 13;
Аспект 13. а = 185, m = 16; Аспект 14. = 14, m = 9;
Аспект 15. а = 100, m = 11; Аспект 16. а = 484, m = 15;
Аспект 17. а = 153, m = 61; Аспект 18. а = 217, m = 19;
Аспект 19. а = 625, m = 25; Аспект 20. а = 624, m = 25;
Задача 3. Напишете пълен и намален система Най-малко