Взаимно простые числа и их свойства

Определение1. Целые числа а₁ ,а₂,…,a_kназываются взаимно-простыми, если (а₁ ,а₂,…,a_k)=1

Определение 2. Целые числа а₁ ,а₂,…,a_k называются попарно взаимно-простыми, если "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, тогда в левой части равенства (*)

(a / d ) & ( b /d ) => (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.

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

Определение 1. Общим кратным конечного множества целых чисел а₁ ,а₂,…,a_k, отличных от нуля, называют целое число m, которое делится на все числа a_i (i=l, 2,…, к)

Определение 2. Целое число (m) называется наименьшим общим кратным чисел а₁ ,а₂,…,a_k, отличных от нуля, если:

1 m - является их общим кратным;

2 (m) делит любое другое общее кратное этих чисел.

Обозначение: m = НОК (а₁ ,а₂,…,a_k) или m = [а₁ ,а₂,…,a_k]

Пример. Даны числа: 2, 3, 4, 6, 12.

Числа 12, 24. 48. 96 являются общими кратными чисел 2, 3, 4, 6, 12 Наименьшим общим кратным будет число 12. т.е.

[2, 3, 4, 6, 12] = 12

НОК определяется однозначно с точностью до порядка следования сомножителей. Действительно, если предположить, что m₁= [а, b] &m₂ = [a, b] Þ (m₁ / m₂) & (m₂/m₁) => [(m₁ = m₂) v (m₁= - m₂)]. Между наименьшим общим кратным и наибольшим общим делителем двух целых чисел существует зависимость, которая выражается формулой: [а, 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<n<а, l<q<a.

Задача 1. Доказать, что если aÎZ и р - простое число, то (а, р) = 1 v (a / р)