3^n == 7 (mod n) и делитель 127

[maxal]

Модификация одной моей старой задачи. Опубликована под номером 4101 в Crux Mathematicorum 42:1 (2016).

Пусть натуральное число $n$ удовлетворяет сравнению:

$$3^n\equiv 7\pmod{n}.$$

Докажите, что $n$ не делится на 127.

[dmd]

Попробую только начать.

Если $n=127m$, то $m$ должно удовлетворять сравнению $m\equiv 115\pmod{126}$. Далее рассуждения должны быть аналогичны теме, с анализом делителей 126 и привлечением квадратичного закона взаимности. Так?

[maxal]

dmd, да.

[dmd]

$n$ должно быть нечётно, значит $21$ должно быть квадратичным вычетом по модулю $m$, и значит символ Якоби $\left(\frac{21}m\right)=1$. Периодичность $\left(\frac{21}m\right)$ - тоже $21$, значит $m$ надо рассмотреть по модулю $21$. Из $m\equiv 115\pmod{126}$ видно, что $m\equiv 10\pmod{21}$. Но $\left(\frac{21}{10}\right)=-1$ - значит $127\nmid n$.

[dmd]

(кстати)

$26782373099$ - решение исходного сравнения

[maxal]

dmd в сообщении #1150203 писал(а):

$26782373099$ - решение исходного сравнения

Да, вот тут ещё: A277126

[dmd]

Решение 9135884036634915191945452485106476242 видимо было получено факторизацией 3^166-7. А как? Я пробовал factor и factorint в pari/gp - не вышло.

[maxal]

dmd, мало пробовали, видимо. Факторизация, кстати, присутствует на factordb.com