kongurencije po modulu p^k

Neka je $p$ neparan prost broj.
Neka je $a=1+kp^\alpha$ , pri čemu $p\not|\,k$ , $k\neq 0$ i $\alpha>0$ .
Neka je $n=mp^\beta$ , pri čemu $p\not |\,m$ .

$a^n=(1+kp^\alpha)^n=\sum_{i=0}^n{n \choose i}k^ip^{i\alpha}$

pošto ne znam kako da izađem na kraj sa ${n\choose i}\pmod p$

računaću $a^n=a^{mp^\beta}\pmod {p^{\alpha+\beta}}$ indukcijom po $\beta$ i pri tom ću koristiti očigledan rezultat:

${p \choose 1}\equiv{p\choose 2}\equiv\ldots\equiv{p\choose p-1}\equiv 0\pmod p$ .

Dakle, ideja je da do $a^n$ stignem iz $\beta+1$ uzastopnih stepenovanja - prvo $\beta$ puta uzastopno stepenujem sa $p$ a na kraju stepenujem i sa $m$ .

Sada je očigledno da za svako $\gamma\in\textbf{Z}^+$ postoji neko $t\in\textbf{Z}^+\setminus p\textbf{Z}$ tako da važi:

$(1+kp^\gamma)^p=1+tp^{\gamma+1}$

Za svako $\gamma\in\textbf{Z}^+$ i $m\in\textbf{Z}^+\setminus p\textbf{Z}$ postoji neko $t\in\textbf{Z}\setminus p\textbf{Z}$ tako da važi:

$(1+kp^\gamma)^m=1+tp^\gamma$

Iz navedenog odmah sledi $p^\beta||n\Leftrightarrow p^{\alpha+\beta}||a^n-1$

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Forum kao aplikacija na telefonu

Srodne teme