Ведение в теорию чисел (Задание №18)

Деление с остатком для целых чисел

Утверждение
Для любых a ∈ Z и b ∈ N, существует представление числа a в виде
a = kb + r, где k ∈ Z, а r — целое число от 0 до b - 1.

Определение
При этом число r называется остатком от деления a на b, а k — неполным частным.

Делимость. Свойства делимости

Определение
Говорят, что натуральное число a делится на натуральное число b, если существует такое натуральное число k, что a = kb. Делимость обозначается следующим образом: a ⋮ b, то есть a кратно b. При этом число b называется делителем числа a, число a — кратным числа b.

Свойства делимости

Любое натуральное число делится на 1 и на само себя.
Если натуральное число a делится на натуральное число b, и число b делится на a, то a = b.
Если a₁ ⋮ b и a₂ ⋮ b, то a₂ + a₁ ⋮ b и a₂ - a₁ ⋮ b.
Если a ⋮ b и c ∈ N, то ac ⋮ b.

Свойства делимости

1) Любое число можно разделить на 1 без остатка. Частным при делении на является само число:

a : 1 = a.

2) Любое число можно разделить само на себя без остатка. Частным при делении числа на само себя является 1:

a : a = 1.

3) Ноль делится на любое число, кроме нуля, без остатка. Частным при делении нуля на любое число является ноль:

0 : a = 0.

4) Делить на 0 нельзя!

Простые и составные числа

Определение
Натуральные числа, имеющие ровно два различных делителя (единицу и само это число), называются простыми.

Определение
Натуральные числа, которые можно разложить в произведение двух множителей, больших единицы, называются составными.

Решето Эратосфена
Для того чтобы найти все простые числа, не превосходящие некоторого натурального n, можно воспользоваться следующим алгоритмом. Выписать подряд все целые числа от 2 до n. Обвести двойку и вычеркнуть все остальные числа, делящиеся на 2 (4, 6, 8, …). Затем обвести первое невычеркнутое число и вычеркнуть все остальные числа, делящиеся на него. И продолжать эту процедуру, пока не будет достигнут конец списка. Теперь все невычеркнутые числа в списке — простые.

Алгоритм проверки числа на простоту
Для того чтобы проверить, является ли число простым, необязательно проверять, что оно не делится ни на одно число меньше его. Достаточно проверить, что число не делится ни на одно из простых чисел, квадрат которых не превосходит рассматриваемое число.

Теорема
Простых чисел бесконечно много.

Основная теорема арифметики

Основная теорема арифметики
Любое натуральное число, отличное от 1, единственным образом (с точностью до порядка сомножителей) можно представить в виде произведения простых множителей.

Алгоритм Евклида

Утверждение

Для любых двух натуральных чисел a > b верно следующее равенство:

НОД(a, b) = НОД(a - b, b).

Теорема
Для любых натуральных a и b найдутся такие целые x и y, что

xa + yb = НОД(a, b).

Наибольший общий делитель

Определение

Наибольшим общим делителем двух натуральных чисел называют такое наибольшее натуральное число, на которое нацело делятся два данных числа. Если наибольший общий делитель двух натуральных чисел равен 1, то такие числа называют взаимно простыми.

Наименьшее общее кратное

Определение

Наименьшим общим кратным двух натуральных чисел называют такое наименьшее натуральное число, которое нацело делится на каждое из данных двух чисел.

Связь между НОД и НОК
Для любых двух натуральных чисел a, b верно следующее равенство:

НОД(a, b) * НОК(a, b) = ab

Линейные диофантовы уравнения с двумя неизвестными

Определение
Линейным диофантовым уравнением с двумя неизвестными называют уравнение вида Ax + By = C, где A, B, C — заданные целые ненулевые числа, x и y — неизвестные целые числа.