Основные понятия теории чисел. Лекция 9
Обозначения: − N - множество натуральных чисел: целые положительные числа вида 1,2,…; − Z - множество целых чисел: числа вида n, -n и 0, где n - натуральное число; − Q - множество рациональных чисел: числа вида p/q, где p и q - целые числа и . Число а делится на число b 0, если существует число q такое, что Число b - делитель числа а, число а - кратное числа b, число q - частное от деления а на b. Утверждение о том, что b делит а обозначают символом . Если b не делит а, то этот факт обозначают . Лемма 1. Если и , то . Лемма 2. Если m=a+b, d/m и d/a, то d/a. Общим делителем двух или нескольких чисел называется число, являющееся делителем каждого из этих чисел. Наибольшим общим делителем (НОД) чисел называется наибольший из их общих делителей - обозначается как Число n>1 называется простым, если оно не имеет других делителей, кроме 1 и n. Например, числа 2, 3, 5, 7 являются простыми, т.к. они делятся только на 1 и на самих себя. Число n называется составным, если оно имеет делитель, отличный от 1 и n. Например, числа 4, 6, 8 − составные числа. Если НОД , то числа называют взаимно простыми. Например: (2,5)=1; (10,21)=1. Лемма 3. Если целое число b взаимно просто с каждым из целых чисел , то b взаимно просто с их произведением Теорема о делении с остатком. Если а и b целые числа, и b>0, то существуют единственные целые числа q и r такие, что a=b x q+r, Число q называют неполным частным при делении a на b, число r называют остатком от деления а на b. Лемма 4. Наименьший, отличный от единицы, делитель натурального числа n>1 есть простое число. Следствие. Каждое натуральное число n>1 имеет хотя бы один простой делитель. Лемма 5. Если p - простое число, то любое целое число а либо взаимно простое с р, либо делится на р, т.е. р/а. Основная теорема арифметики. Любое натуральное число n>1 представляется в виде произведения простых чисел, причем, единственным образом. Разложение числа n на простые сомножители: Пусть p1,…,pк − различные из чисел p1,…,pr (r>k), a α1,…,αk − кратности, с которыми они входят в исходное разложение. Тогда это разложение можно записать в виде: и называется оно каноническим разложением числа n на простые множители. Пример. Согласно теореме Евклида, множество простых чисел бесконечно. Решето Эратосфена : − напишем одно за другим числа 2,3,…N; − число 2 является простым − оставляем, и зачеркиваем после него все числа, кратные 2, т.е. все четные числа; − следующим за числом 2 является число 3, которое является простым. Оставляем 3, зачеркиваем все числа, кратные 3; − продолжая этот процесс, находим все простые числа, не превышающие заданного числа N. Например, N=40: 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40. Простые числа: 2,3,5,7,11,13,17,19,23,29,31,37. Особый класс простых чисел составляют числа вида - простые числа Мерсенна В 1992 г. найдено 32−е число Мерсенна (Его запись содержит 227 832 цифры и требует около ста страниц текста). Длина десятичной записи предыдущего открытого числа была 9808358.
