Используйте маленькую теорему Ферма для решения уравнения $x^{13} \equiv 2\;(\mod\ 23)$ - Математика
Купить гитару в Москве
0 голосов
/

Я должен использовать маленькую теорему Ферма для решения уравнения $$x^{13} \equiv 2\;(\mod\ 23)$$ Но я понятия не имею, как это сделать. Я понимаю, что $2^{23} \equiv 2\;(\mod\ 23)$. Но я не знаю, как решить, о чем вопрос.

Ответы [ 4 ]

3 голосов
/

Маленькая теорема Ферма говорит, что если $x$ относительно простое число по отношению к $23$, то $x^{22}\equiv1\pmod{23}$.

Более того, $$13\times17=221=22\times10+1.$$ Так что если $$x^{13}\equiv2\pmod{23},$$, то $$(x^{13})^{17}\equiv x^{22\times10+1}\equiv x^{1}\equiv2^{17}\pmod{23}.$$ Теперь $$\begin{align}2^2&\equiv4\\2^4&\equiv16\\2^8&\equiv256\equiv3\\ 2^{16}&\equiv9\end{align}.$$ Так$2^{17}\equiv18\pmod{23}$. Как следствие, мы находим, что $18$ является решением $x^{13}\equiv2\pmod{23}$.


Надеюсь, это поможет.

0 голосов
/

Другой подход:

$x^n=2+23k$

Это уравнение может иметь множество решений;например (k = 1, n = 2, x = 5) или (k = 13, n = 2, x = 18), который удовлетворяет следующей конгруэнции:

$x^2≡2 \mod 23$

Если(x, 23) = 1, тогда:

$x^{22}=(x^{11})^2 ≡ 1 \mod 23 $, ⇒ $x^{11}≡ 1 \mod 23$

$x^{11}\times x^2=x^{13}≡2 \mod 23$

Например, набор решений для конгруэнтности $a^n ≡ 2 \mod 23$это:

$5^2, 5^{13}, 5^{13+11}=5^{24}, 5^{35}, . . .$

Другой набор решений:

$18^2, 18^{13}, 18^{24}, 18^{35}, . . .$

так что для вашего вопроса х = 5 и х = 18 икак правило, все числа, для которых их квадраты имеют остаток 2 при делении на 23, являются решениями.

0 голосов
/

Если вам интересно, вы можете использовать дискретный журнал : $$x^{a} \equiv b\pmod{p} \Rightarrow a\log_rx\equiv \log_rb\pmod{p} \Rightarrow x\equiv r^{\frac{\log_rb}{a}}\pmod{p}$$

К сожалению, это работает только тогда, когда $p$ является простым.

0 голосов
/

Найдем $a,b$ таким, что $13a+22b=1,$

По наблюдениям $b=3, a=-5$

Используя маленькую теорему Ферма,

$$x=x^{22(3)-5(13)}=(x^{22})^3(x^{13})^{-5}\equiv1^3\cdot2^{-5}\pmod{23}$$

Давайте найдем $c,d$ такой, что $-32c+23d=1\implies c\equiv32^{-1}\pmod{23}$

Используйте мой метод из Решение линейной конгруэнции

Или используя маленькую теорему Ферма, $2^{-5}\equiv2^{17}\pmod{23}$

...