Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Делимость чисел
Говорят, что натурально число a делится на натуральное число b, если найдется такое целое число k, что a=kb, и записывают следующим образом: a⋮b. При этом число b называется делителем числа a, а число a — кратным числу b.
Любое натуральное число делится на 1 и на само себя.
Если натурально число a делится на натуральное число b, и число b делится на a, то a=b.
Числа делящиеся на 2 называются четными, не делящиеся — нечетными.
Свойства делимости 1) Если a1⋮b и a2⋮b, то a1+a2⋮b и a1–a2⋮b.
2) Если a⋮b и c∈Z, то ac⋮b.
Доказательство. 1) Пусть a1,a2⋮b, тогда существуют k1,k2∈Z: a1=k1b, a2=k2b.
a1+a2=k1b+k2b=(k1+k2)b=kb,k∈Z.
Значит, a1+a2⋮b. Аналогично для разности.
2) Пусть a⋮b, тогда a=kb, ac=kcb=k′b, k′∈Z. Значит, ac⋮b.
Остатки. Для любых a∈Z и b∈N, существует представление числа a в виде:
a=kb+r,
где k∈Z, а r — целое число от 0 до b–1. При этом число r называется остатком от деления a на b, а k — неполным частным.
Простые и составные числа
Простые числа. Натуральные числа имеющие ровно два делителя (единицу и само это число) называются простыми .
Составные числа. Все числа кроме простых и единицы называются составными.
Составное число всегда можно разложить на два множителя отличных от 1.
Задача. Найти все натуральные p такие, что p, p+2, p+4 — простые.
Ответ: 3.
Решение. Пусть есть другое решение. Тогда ни одно из чисел p, p+2, p+4 не делится на 3. Но если p+4 не делится на 3, то и p+1 не делится на 3. Откуда получаем, что p, p+1 и p+2 не делятся на 3, чего быть не может.
Количество простых чисел. Простых чисел бесконечно много.
Доказательство. Предположим, что простых чисел конечное число:
2,3,5,7,11,…,p,
где p — самое большое простое число.
Составим число n:
n=2⋅3⋅5⋅7⋅11⋅…⋅p+1.
Это чисто не делится на 2, так как оно отличается на 1 от числа делящегося на 2. Так же оно те делится на 3, на 5, … на p. Значит число n не делится ни на одно простое число, что противоречит основной теореме алгебры. Полученное противоречие показывает, что наше предположение неверно и простых чисел бесконечно много.}
Решето Эратосфена. Для того, чтобы найти все простые числа не превосходящие некоторого натурального n можно воспользоваться следующим алгоритмом. Выписать подряд все целые числа от двух до n. Обвести двойку, и вычеркнуть все остальные числа делящиеся на 2 (4, 6, 8, … ). Затем, обвести первое не вычеркнутое число, и вычеркнуть все остальные числа делящиеся на него. И продолжить это процедуру пока не достигнется конец списка. Теперь все не вычеркнутые числа в списке — простые.
Алгоритм проверки числа на простоту. Для того чтобы проверить является ли число простым необязательно проверять, что оно не делится ни на одно число меньшее его. Достаточно проверить, что число не делится ни на одно из простых чисел, квадрат которых не превосходит рассматриваемое число.
Основная теорема арифметики
Любое натуральное число, отличное от 1, единственным образом (с точностью до порядка сомножителей) можно разложить на произведение простых множителей.
Каноническое разложение на множители. Из основной теоремы арифметики следует, что различные представления одного и того же составного числа в виде произведения простых чисел связаны только с различием в порядке множителей. Так, например, разложение числа 210 на простые множители может иметь вид 210=2⋅5⋅3⋅7 или 210=2⋅3⋅7⋅5.
Для того чтобы избежать такой неоднозначности принято записывать простые множители в порядке возрастания. При этом если встречаются одинаковые простые множители, то в записи для краткости используют обозначение степени.
Такую упорядоченную запись назвали каноническим разложением числа на простые множители. Например, каноническое разложение числа 210 имеет вид: 210=2⋅3⋅5⋅7, а для числа 90 каноническое разложение таково: 90=2⋅32⋅5.
Малая теорема Ферма
Утверждение. Пусть ka≡kb (mod m), k и m взаимно просты. Тогда a≡b (mod m).
Доказательство. Если ka≡kb (mod m), то ka–kb⋮m, то есть k(a–b)⋮m. Так как k и m взаимно просты, то a–b⋮m, что и значит a≡b (mod m).
Утверждение. Пусть ka≡kb (mod km). Тогда a≡b (mod m).
Доказательство. Если ka≡kb (mod km), то ka–kb⋮km, то есть k(a–b)⋮km. Значит a–b⋮m и a≡b (mod m).
Утверждение. Пусть a≡b (mod m). Тогда НОД(a,m)=НОД(b,m).
Доказательство. Так так a≡b (mod m), то a–b⋮m, то есть a–b=kn. Тогда любой общий делитель a и n является делителем b, а любой общий делитель b и n — делитель a. Поэтому множество общих делителей a и n и множество общих делителей b и n — это множество общих делителей всех трех чисел. Наибольшее число в этом множестве — это, с одной стороны, НОД(a,m), а с другой стороны, НОД(b,m). Поэтому они равны.
Малая теорема Ферма. Пусть p — простое число, тогда для любого натурального n
np–n⋮p.
Доказательство. Если n⋮p, то утверждение очевидно. Пусть теперь n не делится на p. Рассмотрим остатки r1, r2, … rp–1 от деления чисел n, 2n, … (p–1)n на p. Из первого утверждения этого пункта следует, что все остатки различны. А так как их ровно (p–1), то среди них присутствуют все числа от 1 до (p–1). Поэтому
n⋅2n⋅…⋅(p–1)n≡r1⋅r2⋅…⋅rp–1=1⋅2⋅…⋅(p–1) (mod p).
(p–1)!⋅np–1≡(p–1)! (mod p).
Так как (p–1)! и p взаимно просты, то np–1≡1 (mod p), что равносильно утверждению теоремы.