1999 Является простым числом, так как простое число – это число, которое имеет только два делителя: единицу и само себя.

Производим расчет: . Таким образом мы упростили дробь .

Канонический вид: .

Задание 5. Пользуясь расширенным алгоритмом Евклида вычислить нод и выразить его через исходные числа: (91476; 3960).

НОД (91476; 3960) по алгоритму Евклида (метод деления):

		91476	3960
		91080	23
	3960	396
	3960	10
	0

1. , остаток 396. Продолжаем деление пока остаток не будет равен нулю.

2. остаток 0. Остаток равен нулю, значит НОД равен предыдущему остатку от деления.

Ответ: НОД (91476; 3960) = 396.

Расширенный алгоритм Евклида:

.

Подставим полученные значения в уравнение:

Переносим 396 в левую часть уравнения:

Поделим обе части исходного уравнения на НОД ( ;3960) = 14:

НОД (231;10) = 1.

Коэффициенты уравнения:

Найдём частное решение исходного уравнения, используя цепные дроби

Для этого составим дробь, числителем которой будет наибольший по модулю коэффициент перед x или y, а знаменателем наименьший:

Таким образом, частное решение исходного уравнения имеет один из следующих четырех видов: .

Подставляя четыре значения в исходное уравнение, мы понимаем, что решение: . Уравнение приобретает вид:

(См. замечание, сделанное выше.)

или

НОД (91476;3960) = 396

Выразим НОД через исходные числа:

Пусть a =3960, b= 91476. Тогда

.

Следовательно, исходные числа (-23) и 1.