Взаємно прості числа і їх властивості - студопедія

Визначення 2. Цілі числа а1, а2, ..., ak називаються попарно взаємно-простими, якщо "i, s (i, s = 1, 2. до, i¹s, (аi. Аs) = 1).

Якщо числа задовольняють визначенню 2, то вони задовольняють і визначенню 1. Зворотне твердження в загальному випадку невірно, наприклад: (15, 21, 19) = 1, але (15, 21) = 3

Теорема (критерій взаємної простоти)

(А, b) = 1 <=> $ Х, у ÎZ: ах + by = 1

Доведемо необхідність. Нехай (а, b) = 1. Вище ми показали, що якщо d = (a, b), то $ х, y ÎZ. d = ax + by.

Оскільки в цьому випадку d = 1, то будуть $ х, y ÎZ (які визначаються з алгоритму Евкліда): 1 = ах + bу.

Достатність. Нехай (*) ах + by = 1, доведемо, що (а, b) = 1. Припустимо, що (a, b) = d, тоді в лівій частині рівності (*)

НОК цілих чисел і його властивості.

Визначення 1. Загальним кратним кінцевого безлічі цілих чисел а1, а2, ..., ak. відмінних від нуля, називають ціле число m, яке ділиться на всі числа ai (i = l, 2, ..., к)

Визначення 2. Ціле число (m) називається найменшим спільним кратним чисел а1, а2, ..., ak. відмінних від нуля, якщо:

1 m - є їхнім спільним кратним;

2 (m) ділить будь-яке інше спільне кратне цих чисел.

Приклад. Дано числа: 2, 3, 4, 6, 12.

Числа 12, 24. 48. 96 є спільними кратними чисел 2, 3, 4, 6, 12 Найменшим спільним кратним буде число 12. тобто

НОК визначається однозначно з точністю до порядку проходження сомножителей. Дійсно, якщо припустити, що m1 = [а, b] m2 = [a, b] Þ (M1 / m2) (M2 / m1) => [(m1 = m2) v (m1 = - m2)]. Між найменшим спільним кратним і найбільшим спільним дільником двох цілих чисел існує залежність, яка виражається формулою: [а, b] = ab / (а, b) (виведіть її самостійно)

Цей зв'язок дозволяє стверджувати, що для будь-якої пари цілих чисел, відмінних від нуля, існує їх найменше спільне кратне. Дійсно, (а, b) - завжди можна однозначно вивести з алгоритму Евкліда і за визначенням (а, b) ¹ 0, тоді дріб a × b / (а, b) ¹ 0 і буде визначена однозначно.

Найбільш просто НСК двох цілих чисел обчислюється в тому випадку, коли (а, b) = 1, тоді [а, b] = a × b / 1 = а • b

Наприклад, [21, 5] = 21 × 5/1 = 105, т. К. (21, 5) = 1.

Прості числа та їх властивості.

Визначення 1. Натуральне число (р) називається простим, якщо р> 1 і не має покладе. подільників, відмінних від 1 і р.

Визначення 2. Натуральне число а> 1, що має крім 1 і самого себе інші позитивні подільники, називається складовим.

З цих визначень випливає, що безліч натуральних чисел можна розбити на три класи:

а) складені числа;

б) прості числа;

Якщо а - складене, то а = nq, де 1

Завдання 1. Довести, що якщо aÎZ і р - просте число, то (а, р) = 1 v (a / р)