решить: Докажите, что выражение -1 делится на 997 - вопрос №210211651997 от mnadezhkin 09.12.2020 04:26

Question

Математика: решить: Докажите, что выражение -1 делится на 997

mnadezhkin · Answer

Следует, во-первых, показать, что 997 является простым числом. Делается это так: у любого составного числа есть хотя бы один делитель, отличный от единицы, не превосходящий $\sqrt{n}$ . В самом деле, если такого делителя нет, то найдутся два делителя, больших $\sqrt{n}$ , а это невозможно. Поэтому достаточно проверить наличие делителей от до $\lfloor \sqrt{997}\rfloor = 31$ . Из них нужно проверять только простые: 2,3,5,7,11,13,17,19,23,29,31 , что сделать уже совсем нетрудно.

По малой теореме Ферма мы знаем, что $x^{996}\equiv 1\mod 997,\; x = \overline{1,996}$ . $97^{498} \equiv (997-900)^{498}\equiv 900^{498} \equiv 9^{498}\cdot 100^{498}\equiv 3^{996}\cdot 10^{996}\equiv 1\mod 997$ .