Aritmetica modulare

[picchi]

Buongiorno!! vi posto una breve dimostrazione di una proposizione!! vorrei capire come mai si giunge al risultato...

Siano $p$, $q$ due primi distinti e sia $n=p*q$ e $\varphi(n)=(p-1)*(q-1)$ (funzione di Eulero). Sia $e$ $in$ $NN$ tale che $(e, \varphi(n))=1$, allora $EE$ $d$ tale che $ed-=1 mod\varphi(n)$. Vogliamo dimostrare che se $(P,p)=p$ e $(P,q)=1$ allora $P^(ed)-=P mod n$.

Osserviamo, anzitutto, che $ed-=1$ $mod\varphi(n)$ implica $ed=1+j*\varphi(n)$ per qualche intero $j$.
Per il piccolo Teorema di Fermat, $P^(q-1)-=1 mod q$, perciò elevando primo e secondo membro a $p-1$
$(P^(q-1))^(p-1)-=1 mod q$, cioè
$P^(\varphi(n))-=1 mod q$ ed elevando primo e secondo membro per $j$ e moltiplicando per $P$,
$P^(j*\varphi(n)+1)-=P mod q$, quindi
$P^(ed)-=P mod q$, da qui si ha
$q|P^(ed)-P$
Ma $p|P$ per hp. (!!! questa è l'implicazione non chiara!!!) perciò $p|P^(ed)-P$, quindi $P^(ed)-=P mod p$
Da qui si giunge (chiaramente) alla dimostrazione del Teorema.
Ciò che non è chiaro è appunto l'implicazione precedente!!!
Potete aiutarmi? grazie!

[mistake89]

Se $p|P$ per ipotesi (essendo il loro MCD pari a $p$) allora $p$ dividerà ogni potenza di $P$ (banalmente in quanto le potenze sono del tipo $P*...*P$). Quindi potresti raccogliere $P$ ed avere l'asserto. Puoi scrivere infatti $P^(ed)-P=P(P^(ed-1)-1)$ che ovviamente è diviso da $p$