Тема 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. Что называется НОД целых чисел? Что называется НОК целых чисел? Чему равен НОД двух чисел, записанных в канонической форме? Чему равно НОК целых чисел, записанных в канонической форме? Какая формула связывает НОД и НОК двух целых чисел? Верно ли, что если , то ? |
| Оглавление| |