Слишком сложно? Тогда запросите консультацию специалиста!
Наша компания занимается тем, что помогает студентам выполнять различные учебные работы на заказ. Вы можете ознакомиться с перечнем выполняемых работ, а так же с их стоимостью на странице с ценами.
Определение1. Целые числа а1 ,а2,…,akназываются взаимно-простыми, если (а1 ,а2,…,ak )=1
Определение 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, тогда в левой части равенства (*)
(a /d)& (b /d)=> (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.
НОК целых чисел и его свойства.
Определение 1. Общим кратным конечного множества целых чисел а1 ,а2,…,ak, отличных от нуля, называют целое число m, которое делится на все числа ai (i=l, 2,…, к)
Определение 2. Целое число (m) называется наименьшим общим кратным чисел а1 ,а2,…,ak, отличных от нуля, если:
1 m - является их общим кратным;
2 (m) делит любое другое общее кратное этих чисел.
Обозначение: m = НОК (а1 ,а2,…,ak) или m = [а1 ,а2,…,ak]
Пример. Даны числа: 2, 3, 4, 6, 12.
Числа 12, 24. 48. 96 являются общими кратными чисел 2, 3, 4, 6, 12 Наименьшим общим кратным будет число 12. т.е.
[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<n<а, l<q<a.
Задача 1. Доказать, что если aÎZ и р - простое число, то (а, р) = 1 v (a / р)
