eulero-fermat

[max tre]

Nella tesina avevo intenzione di parlare dell'aritmetica modulare e siccome voglio mostrare che non è solo una sega mentale ma trova applicazioni utili volevo mostrare il funzionamento del sistema rsa.
Il funzionamento non è complicato, ma volevo anche dimostrare i teoremi che ci stanno sotto.
In particolare non riesco a dare una dimostrazione completa del teorema di eulero-fermat...
Se mi limitassi a dimostrare la validità nel caso $ n=pq $ con $ p,q $ primi (che poi è quello che mi interessa), andrebbe bene questo?
1 Dimostro il piccolo teorema di fermat per induzione
2 Ho come ipotesi che $ (a,p)=1\rightarrow a^p\equiv a(\mod p) $
3 La mia tesi è che $ n=pq,(a,n)=1\rightarrow a^{\phi (n)}\equiv 1 (\mod n) $
4 Noto che $ \phi (n)=\phi (pq)=pq-p-q+1=(p-1)(q-1) $ poiché n è divisibile, oltre che per 1 (con cui è comunque coprimo), solo per i q multipli di p e per i p multipli di q, cui va sottratto un’unità poiché n viene così contato due volte
5 Riscrivo $ \phi (n)=(p-1)(q-1) $ come $ \phi (n)=p(q-1)-(q-1) $ (la scrittura precedente mi serviva per come ho definito $ d $ ed $ e $ nel sistema rsa
6 $ a^{\phi (n)}=\frac{a^{p(q-1)}}{a^{q-1}}=\frac{(a^p)^{q-1}}{a^{q-1}}\equiv \frac{a^{q-1}}{a^{q-1}}=1 (\mod p) $ dove ho sfruttato fermat
7 $ a^{\phi (n)}\equiv 1(\mod p) \rightarrow a^{\phi (n)}\equiv 1(\mod n) $ poiché $ n=pq $
Mi pare strano che torni tutto, in particolare non ho usato il fatto che $ a $ e $ n $ sono coprimi...
Ho dubbi in particolare sul punto 6, non vorrei aver confuso uguaglianze ed equivalenze, $ \mod p $ e $ \mod n $...

[paga92aren]

Non puoi usare le frazioni con le congruenze. Puoi però moltiplicare per l'inverso del denominatore $d^{-1}$, ma per farlo deve esistere l'inverso di un elemento. L'inverso esiste se e solo se $(d,n)=1$.
Inoltre quando imponi $n=pq$ ti limiti a un caso particolare del teorema (ma se serve solo per rsa allora dovrebbe bastare).
Fra il punto 6 e il 7 va detto che lo stesso ragionamento vale per $q$ e poi applichi il teorema cinese del resto.
Per il resto mi sembra corretto.

[max tre]

Sperando di non sparare altre eresie, detto che $ (a,n)=1 $ - cosa che era tra le ipotesi - , per calcolare l'inverso come dovrei fare?
Tipo, l'inverso di $ 3 (\mod 5) $ è $ x|3x\equiv 1 (\mod 5) $, ovvero $ 3x-5y=1 $, da cui mi so ricavare (ad esempio, con l'algoritmo di euclide, ma qui basta andare ad occhio) $ x=2 $, ma questo non mi serve a niente (credo) per la dimostrazione, visto che non riesco a scrivere x in funzione di 3 o di 5 (almeno, per adesso non mi viene in mente come fare)
Comunque, io cercavo una dimostrazione il più facile possibile di tutto quello che mi serve, in questo caso il teorema di eulero-fermat nel caso $ n=pq $
In particolare, volevo evitare l'odiato teorema cinese visto che non ne so la dimostrazione e penso di non averlo neanche mai capito...

[max tre]

e se scrivo $ a^{\phi (n)}=a^{p(q-1)}a^{1-q}\equiv a^{q-1}a^{1-q}\equiv 1 (\mod p) $ ha senso?
voglio dire, c'è un motivo per cui posso spezzare $ \phi (n) $ o quando scrivo $ a^{1-q} $ scrivo qualcosa privo di senso nelle congruenze?

[Sonner]

Puoi anche non chiamarlo teorema cinese del resto, è semplicemente questo fatto:
$ p\mid n $ e $ q\mid n \rightarrow pq\mid n $. Ora poni $ n=a^{(p-1)(q-1)}-1 $ e hai finito (le ipotesi valgono per Fermat)

[max tre]

$ p\mid n $ e $ q\mid n \rightarrow pq\mid n $

Beh, io avevo limitato già all'inizio $ n=pq $

Ora poni $ n=a^{(p-1)(q-1)}-1 $ e hai finito (le ipotesi valgono per Fermat)

Questa sarebbe la mia tesi; lo so che sono tardo ma mi manca un passaggio

[dario2994]

$p|(a^{q-1})^{p-1}-1$ e $q|(a^{p-1})^{q-1}-1$ per Fermat, quindi $pq|a^{(p-1)(q-1)}-1$

[max tre]

Intanto grazie 1000

$p|(a^{q-1})^{p-1}-1$ e $q|(a^{p-1})^{q-1}-1$ per Fermat

Questo è perché da $ a^{p}\equiv a (\mod p) $ e visto che $ (a,p)=1 $ dividi per $ a $ (o moltiplichi per il suo inverso?) a sinistra e a destra, giusto?

quindi $pq|a^{(p-1)(q-1)}-1$

E questo è perché p e q sono primi diversi e hai appena detto che entrambi dividono $ a^{(p-1)(q-1)}-1 $, giusto?

Quindi io dovrei prima dire questo e poi dire che $ \phi (n)=(p-1)(q-1) $, quindi $ a^{\phi (n)}\equiv 1 (\mod n) $ (ovviamente per $ n=pq $), giusto?

[dario2994]

Intanto grazie 1000

$p|(a^{q-1})^{p-1}-1$ e $q|(a^{p-1})^{q-1}-1$ per Fermat

Questo è perché da $ a^{p}\equiv a (\mod p) $ e visto che $ (a,p)=1 $ dividi per $ a $ (o moltiplichi per il suo inverso?) a sinistra e a destra, giusto?

quindi $pq|a^{(p-1)(q-1)}-1$

E questo è perché p e q sono primi diversi e hai appena detto che entrambi dividono $ a^{(p-1)(q-1)}-1 $, giusto?

Quindi io dovrei prima dire questo e poi dire che $ \phi (n)=(p-1)(q-1) $, quindi $ a^{\phi (n)}\equiv 1 (\mod n) $ (ovviamente per $ n=pq $), giusto?

Tutto giusto