Тема 4. наибольший общий делитель и наименьшее общее кратное и способы их нахождении. взаимно-простые числа

     Определение 4.1. Общим делителем целых чисел a1, a2,…, an называется любое целое число d, такое что d½а1, d½а2,…, d½аn.

     Пример.  

Числа 30, 165,45 имеют общими делителями числа 3, -3, 15, -15.

     Определение 4.2.   Наибольшим общим делителем (НОД) целых чисел   a1, a2,…, an называется такой их положительный общий делитель, который делится на любой другой общий делитель этих чисел.

     Обозначение: если d есть НОД чисел  a1, a2,…, an , то это записывается следующим образом:  (a1, a2,…, an ) = d

Таким образом, из определения 3.2., если  (a1, a2,…, an ) = d, то

            1) d> 0,

            2) d½а1, d½а2,…, d½аn,

            3) если существует целое  число k, такое что k½a1, k½a2,…, k½an, то k½d.

     Рассмотрим основные свойства НОД целых чисел.

     Теорема 4.3.  1) Для любых целых чисел    a1, a2,…, an , из которых хотя бы одно отлично от нуля, существует НОД. 2) Если   , где

 р1, …, рs – различные простые числа, то (a1, a2,…, an ) = .

     Теорема 4.4.   Если   (a1, a2,…, an ) = d, b½d  и b>0, то  .

     Теорема 4.5.   (a1,…, an-1, an) = ((a1,…, an-1), an).

НОД n чисел (n³ 3) можно найти, найдя сначала НОД n-1 чисел , и взяв затем НОД от полученного таким образом числа d= (a1,…, an) и последнего числа an.

     Замечание 4.6.  Из Т. 4.3. следует способ нахождения НОД целых чисел, а именно: 1) разложить каждое число на простые множители, записав разложение в каноническом виде; 2) найти произведение минимальных степеней простых множителей, входящих в разложения.

     Пример.

Найти НОД чисел 5775, 15246, 399.

Разложим числа на простые множители

Найдем произведение минимальных степеней простых чисел, входящих в разложения.

 , таким образом 

     Определение 4.7.  Пусть  a1, a2,…, an – отличные от нуля целые числа. Наименьшим общим кратным (НОК) называют наименьшее положительное число, делящееся на все эти числа.

     Обозначение 

Таким образом, если  , то

,

 ,

если  и , то .

     Теорема 4.8.   Если   - каноническое разложение чисел a1, a2,…, an на простые множители, то

                               =

     Теорема 4.9.   Пусть - целые, , тогда .

     Определение 4.10.  Числа а и b называются взаимно простыми, если НОД этих чисел равен 1.

     Теорема 4.11.   Если a и  p – целые числа, причем  p-простое, то либо  , либо числа  a и  p взаимно просты.

     Теорема 4.12.  НОК двух взаимно простых чисел равно их произведению.

     Теорема 4.13. Для того чтобы a делилось на взаимно простые числа  b и  c, необходимо и достаточно, чтобы оно делилось на их произведение.

     Теорема 4.14.  Если , причем , то .

Задания для самостоятельного решения

Каким может быть наибольший общий делитель по сравнению с их разностью?

Доказать, что два последовательных нечетных числа взаимно простые.

Доказать, что наибольший общий делитель последовательных чётных чисел равен 2.

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

Доказать, что если числа а и с взаимно простые, то каждое из этих чисел взаимно простое с суммой и разностью данных чисел.