Факторизация числа (11 кл.)

Обозначим a=3481, b=4120, N=26069. Известно, что остаток от деления числа на N равен a. Найдите разложение числа N на простые множители.

• Подсказка

Подсказка

Нужно увидеть, что после чего получить и использовать то обстоятельство, что пары чисел (b-59) и N или (b+59) и N имеют общие делители.
• Решение

Решение

Заметим, что Тогда . Следовательно, пары чисел (b-59) и N или (b+59) и N имеют общие делители, отличные от 1. Найдём наибольший общий делитель чисел (b+59) и N по алгоритму Евклида. 

26069=6∙4179+995, 

4179=4∙995+199,

995=5∙199.

Следовательно, НОД((b+59),N)=199 – простое число. Остаётся разделить N на 199 и убедиться, что частное - также простое число.
• Ответ

Ответ

26069=131∙199.