Question

Помогите решить:

Докажите, что выражение $97^{498}$-1 делится на 997

Answer 1

Следует, во-первых, показать, что $997$ является простым числом. Делается это так: у любого составного числа $n$ есть хотя бы один делитель, отличный от единицы, не превосходящий $\sqrt{n}$. В самом деле, если такого делителя нет, то найдутся два делителя, больших $\sqrt{n}$, а это невозможно. Поэтому достаточно проверить наличие делителей от $2$ до $\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$.