Решить сравнение

Одним из способов решения могло быть использование таблиц индексов по модулю 125. Они есть в приложении к ряду учебников или задачников. Но здесь можно обойтись и без них.

Прежде всего, решим сравнение по модулю 25. Это намного проще -- с учётом того, что 74 сравнимо с -1 по этому модулю. Надо выяснить, когда $%x^2+1$% делится на 25, и тут сразу ясно, что подходят числа 7 и -7. Нетрудно понять, что по модулю 25 других решений нет, так как если $%y$% -- ещё одно решение, то $%x^2-y^2$% делится на 25. Из этого следует, что один из сомножителей делится на 25: если бы оба они делились на 5, то оказалось бы, что $%2x=(x-y)+(x+y)$% тоже делится, но у нас это не так.

Заметим, что исходное сравнение имеет решение $%-x$% вместе с каждым решением $%x$%. Поэтому можно ограничиться разбором случая $%x=25k-7$%, где $%k$% целое. После возведения в квадрат будет $%x^2=5^4k^2-350k+49$%, и это число сравнимо с 74 по модулю $%5^3$%. Таким образом, $%25k$% сравнимо с $%25=74-49$% по модулю $%5^3$%, и это значит, что $%k$% сравнимо с единицей по модулю 5. Полагая $%k=5m+1$% для целого $%m$%, получаем $%x=125m+18$%. Таким образом, решениями по модулю 125 будет числа $%\pm18$%. Число с минусом можно заменить на положительное, то есть $%x\equiv18,107\pmod{125}$%.