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

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

• Подсказка

Подсказка

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

Решение

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

7169=26∙268+201, 

268=201+67,

201=3∙67.

Следовательно, НОД((b+27),N)=67 – простое число. Остаётся разделить N на 67.
• Ответ

Ответ

7169=67∙107.