Matematické Fórum

byk7 · 20. 03. 2011 11:23

Mějme funkci $f:\mathbb{N}\to\mathbb{N}_0$ kterou definujeme $f(x):=A^x\pmod B$ s podmínkami $A,B\in\mathbb{N}$ a $A<B$ .

Potom dokažte, že pro $x_{1,2}\in\mathbb{N}$ platí $f^{\,x_2}\left(x_1\right)\equiv f^{\,x_1}\left(x_2\right)\pmod B.$

Přiznám se, že řešení neznám, ale přijde mi to jako zajímavý problém.

Stýv · 20. 03. 2011 11:29

$f^n$ značí skádání fcí?

byk7 · 20. 03. 2011 11:41

Ne, značí to mocninu.
$f^{\,x_2}\left(x_1\right)=\Bigl(f\left(x_1\right)\Bigl)^{\,x_2}.$

Pavel Brožek

Značení Zobrazit/skrýt!

$f(x_1)&=A^{x_1}\mod B\\ f^{x_2}(x_1)&=(A^{x_1}\mod B)^{x_2}\\ f^{x_2}(x_1)\mod B&=(A^{x_1}\mod B)^{x_2}\mod B=(A^{x_1})^{x_2}\mod B$

Stejně se ukáže i

$f^{x_1}(x_2)\mod B&=(A^{x_2})^{x_1}\mod B$ .

Protože platí $(A^{x_1})^{x_2}=(A^{x_2})^{x_1}$ , máme

$f^{x_1}(x_2)\equiv f^{x_2}(x_1)\pmod B.$

byk7 · 20. 03. 2011 12:05

↑ Pavel Brožek:
pěkné, díky,

ale není mi jasné, jak jsi se dostal od $\Bigl(A^{\,x_1}\pmod B\Bigr)^{\,x_2}\pmod B$ k $\left(A^{\,x_1}\right)^{\,x_2}\pmod B$ ?

Pavel Brožek · 20. 03. 2011 12:14

Máme tedy ukázat $(a\mod n)^b\mod n=a^b\mod n$ . Pro nějaké celé $y$ a $x\in\{0,\ldots,n-1\}$ určitě platí $a=x+ny$ .

$(a\mod n)^b\mod n=(x+ny\mod n)^b\mod n=x^b\mod n$

$a^b\mod n=(x+ny)^b\mod n=x^b+(\ldots)n\mod n=x^b\mod n$

Na rozepsání $(x+ny)^b$ se přitom použila třeba binomická věta nebo jednoduše

$(x+ny)^b\equiv(x+ny)\cdot(x+ny)^{b-1}\equiv x\cdot(x+ny)^{b-1}\equiv\ldots\equiv x^b\pmod n.$