Пълен и намалена система остатък, математика, което ми харесва

10. Пълното и понижено система остатък

Определение. Номерата образуват цялостна система на остатъци по модул, ако всяко цяло число еднакви модул с един и само един от тези номера.

Всяка пълна система на остатъци модул се състои от числа, които са взаимно еднакви модул.

Теорема. Да - цялостна система от остатъци по модул. Да - цяло число, което е сравнително премиер да. След това - също цялостна система от остатъци по модул.

Доказателство. Ние трябва да се докаже, че броят на двойки еднакви по модул. Да приемем, напротив. нека

Тъй като ГРУ, това, което е в противоречие.

Теорема. Да - цялостна система от остатъци по модул. Да - цяло число. След това - също цялостна система от остатъци по модул.

Лема. Ако, след GCD ГРУ.

А-В = км \ к "заглавие =" A \ екв б \ pmod \ Longrightarrow а-б \ vdots m \ Longrightarrow
а-б = км \ к "стил =" вертикално подравняване: -4px; граница: няма; "> - цяло число.

Тук. Всеки общ делител и делител. Следователно GCD GCD.

Определение. Numbers образуват намалява по модул система остатък, ако те са взаимно прости с всяко цяло число взаимно прости със сравнима с един и само един от тези номера е модул.

Пример. Намалена система на остатъци по модул 10: 1,3,7,9.

Лема. Всички системата на остатъци модул се състои от еднакъв брой номера, който е определен - функцията Ойлер.

Доказателство. В действителност, се предполага, че има два намалена система остатък модул, състоящ се от различен брой номера:

След това, тъй като формата на намалената система на остатъци по модул, всеки от номерата сравними с един и само един от тези номера. Оттогава принципа на картотекирам, най-малко два от номерата са сравними с някои номер, и следователно, ще бъде подходящ модул. Но това противоречи на факта, че - намалената система на остатъци по модул. Това означава.

Ние сега се докаже, че. В действителност, номера по-малки от и сравнително премиер да формират намалена система на остатъци по модул. Това е следствие от лема.

Определение. функция Ойлер (или totient) означава броя на числа, по-малко от и относително прости за.

Теорема. Ако - намалена система от остатъци по модул и - брой председател с, а след това - също намалява система от остатъци по модул.

Ако - просто, тогава.

Лема. Ако - просто, тогава.

Доказателство. Наистина, цифрите по-малко прости и имат общ делител с него, всичко.

Лема. Нека ГРУ. След това. Мултипликативните функция на Ойлер.

Доказателство. Нека да запишете всички числа от 1 до следното:
123 \ ldotsa \\
а + 1а + 2а + 3 \ ldots2a \\
2а + 12а + 22а + 3 \ ldots3a \\
\ Ldots \\
(В-1) + 1 (Ь-1) + 2 (Ь-1) + 3 \ ldotsab
\ End "заглавие =" \ започне
123 \ ldotsa \\
а + 1а + 2а + 3 \ ldots2a \\
2а + 12а + 22а + 3 \ ldots3a \\
\ Ldots \\
(В-1) + 1 (Ь-1) + 2 (Ь-1) + 3 \ ldotsab
\ End "стил =" вертикално подравняване: -49px; граница: няма; ">

Числата във всеки ред образуват цялостна система от остатъци модул. Така председателят на една от тях. Въпреки това, тези номера са подредени в колони - един под друг, защото всяка колона са числа еднакви модул.

Числата във всяка колона образуват цялостна система от остатъци модул. Всъщност, то колона се получава, като се броят, образуват цялостна система от остатъци модул, ги умножава по броя на нулевия с, и се прибавя към всяка от тях.

По този начин всяка колона точно номера сравнително премиер да.

Тъй като броят им е председател на единствено и само ако то е отлично и е председател на сумата на числата сравнително премиер да, така или иначе.

Доказателство. Според лема на мултипликативна, функция на Ойлер

p_n ^) = \ varphi (p_1 ^) \ varphi (p_2 ^) \ ldots \ varphi (p_n ^). "заглавие =" \ varphi (p_1 ^ p_2 ^ \ ldots
p_n ^) = \ varphi (p_1 ^) \ varphi (p_2 ^) \ ldots \ varphi (p_n ^) "стил =" вертикално подравняване: -6px ;. граница: няма; ">

И тогава ние изчисляваме всеки от лемата за изчисляване на функциите на Ойлер за простите числа.

Теорема (Ойлер). Ако - са сравнително прости числа,

Да - всички намалени система от остатъци по модул. , След това - също намалява система на остатъци модул. Следователно, всеки от номерата на първата последователност е сравнима с един от втората последователност от числа модул, и всеки от броя на втора последователност е сравнима с един от първите номера на последователности. след това

Тъй като всеки от номерата сравнително премиер да, тогава те имат едно сравнение може да бъде намалена:
х ^ к \ equiv1 \ pmod \\
х ^ \ equiv1 \ pmod.
\ End "заглавие =" \ започне
х ^ к \ equiv1 \ pmod \\
х ^ \ equiv1 \ pmod.
\ End "стил =" вертикално подравняване: -16px; граница: няма; ">

Следствие. Да - цели числа - естествено. Ако, ГРУ, а след това.

Доказателство. Да. От тогава - естествено число. след това

Говори се, че един ден, докато Ойлер безсъние изчислява шест степени на първите 100 броя, а резултатите се повтарят в паметта след много дни. В други случаи Ойлер тестване на полученото число от тях, изчислени за първите 20 часа броят на знака след десетичната запетая.

През 1741, Ойлер, по покана на Фридрих II, пристигнали от Санкт Петербург до Берлин академия на науките. Учените взели с голяма чест. На един от кралските приеми в Двореца на царската майка обърна внимание на Ойлер, той й казва, че едносрични "да" и "не". "Защо, ти не искаш да говориш с мен?" - попита тя Ойлер. "Госпожо, - каза ученият - Идвам от страна, където тези, които казват обеси." отговор на Ойлер показва къде трудни условия е трябвало да работят в Санкт Петербург академия на времето.

Видният френски математик Per Ферма (1601-1665) е бил адвокат по професия. В теорията на числата, името му се свързва с известната теорема, Последна теорема на Ферма и малката теорема на Ферма. Геометрията е непосредствена предшественик Farm Декарт. Той играе важна роля в стопанството раждането на теорията на вероятностите. В творбите на Ферма получи системно развитие на диференциация и интеграция. Името на създаването на свързани ферма вариационен принцип на геометричната оптика.

1. докаже, че ако - понижено система на остатъци по модул, след това.

2. Докажете, че ако - просто число, а след това (теорема на Уилсън).

3. Докажете, че ако - просто число, а след това там е цяло число, което се дели на.

4. Докажете, че ако - цяло число, и - странно прост делител от тогава.

5. докаже, че ако - понижено система на остатъци по модул, след това.

6. докаже, че ако - понижено система на остатъци по модул съществува, така че, след това.

7. Намерете остатъци по модул.

8. Докажете, че ако - целите числа и се дели на 30, а след това разделен на 30.

9. Докажете, че ако - числа, и - просто число, а след това.

10 и - различни прости числа. Докажете, че.

11. Докажете, че не разделя изобщо от броя.