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

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

     Пример.  

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

     Определение 3.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.

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

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

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

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

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

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

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

     Пример.

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

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

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

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

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

     Обозначение 

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

,

 ,

если  и , то .

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

                               =

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

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

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

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

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

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

Контрольные вопросы

3.1.     Что называется НОД целых чисел?

Что называется НОК целых чисел?

Чему равен НОД двух чисел, записанных в канонической форме?

Чему равно НОК целых чисел, записанных в канонической форме?

Какая формула связывает НОД и НОК двух целых чисел?

Верно ли, что если , то ?