решить: Докажите, что выражение -1 делится на - вопрос №210202631997 от sdx2312 21.10.2021 02:53

Question

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

sdx2312 · 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$ .