Лабораторная работа № 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. Сократить дробь .