Лабораторная работа № 1 Наибольший общий делитель.
Теорема: Для любых целых чисел 
и 
существует и притом единственная пара целых чисел 
и 
таких, что 
, 
.
При этом число 
называют делимым, 
- делителем или модулем, - частным и - остатком при делении на . Если =0, то говорят что делится на , и в этом случае - является делителем числа , делимое будет кратным числа 
. Наибольший из общих делителей чисел 
называется их наибольшим общим делителем (НОД) и обозначается ().
называется наименьшим общим кратным (НОК) и обозначается []. Отметим, что выполняются следующие рекуррентные формулы:
.
Числа 
называются взаимно простыми, если выполняется условие: (
)=1.
НОД и НОК двух чисел связаны следующим соотношением:
.
Одним из алгоритмов нахождения наибольшего общего делителя чисел является алгоритм Евклида:
1. Пусть 
.
2. Производится последовательное деление:
Последний положительный остаток и будет наибольшим общим делителем чисел a и b.
Пример1. Найти НОД чисел 420, 126, 525.
Решение.
I способ: Найдем НОД чисел 420 и 126, используя алгоритм Евклида.
Получим 420=126*3+42.
126=42*3.
Следовательно, (420, 126)=42. Теперь найдем (42, 525).
525=42*12+21
42=2*21.
Следовательно, (420, 126, 525) =21.
II способ: Вычислим НОД с помощью канонического разложения на простые числа.
Имеем
420|2 126|2 525|5
210|2 63 |3 105|5
105|5 21 |3 21 |3
21 |3 7 |7 7 |7
7 |7 1 1
1
Таким образом 420 = 
, 126 = 
, 525 = 
, следовательно (420, 126, 525) = 
=21, [420, 126, 525] = 
=6300.
Пример 2. Решить систему в натуральных числах 
.
Решение. Т.к. 
, то 
, 
Тогда получим 
, 
.
1) 
;
2) 
3) 
4) 
Ответ: (120, 30); (90, 60); (60, 90); (30, 120).
Задания для самостоятельной работы.
1. Найти наибольшее целое число, дающее при делении на 13 частное 17.
2. Доказать, что: 1) квадрат нечетного натурального числа при делении на 8 дает остаток 1; 2) сумма квадратов двух последовательных натуральных чисел при делении на 4 дает остаток 1.
3. Доказать теорему: если каждое из двух целых чисел при делении на натуральное число дает остаток 1, то их произведение при делении на дает остаток 1.
4. Доказать: если сумма двух трехзначных чисел делится на 37, то и шестизначное число, составленное приписыванием одного из них к другому, также делится на 37.
5. Найти НОД И НОК чисел 187, 153, 221.
6. Доказать, что 
7. Решить систему уравнений в натуральных числах 
8. Сократить дробь 
.