Gruppi e congruenze
Ciao a tutti. Ho due quesiti da porvi.
Il primo mi chiede di dimostrare che n=91 non è primo applicando il Piccolo teorema di Fermat (senza fattorizzarlo).
Ho pensato:
Il PFT dice che, con n numero primo
$x^{n-1} = 1 mod n$
con $mcd(x,n)=1$
Con 91 sarebbe quindi: $x^90 = 1 mod 91$ con $mcd(x,91)=1$
Ecco, adesso come dimostro che quest'ultima congruenza non è vera senza dover fare calcoli spropositati?
Ad esempio con $x=2$, non dovrò mettermi a fattorizzare $2^90$ e moltiplicare le classi resto, dovrebbe esserci una "via" per dimostrarlo.
Per il secondo volevo chiedere più che altro una conferma:
Data la relazione:
$−173 · 371 + 113 · 568 = 1$
Dire se $x=113$ appartiene a (Z*371 non me lo scrive bene, spero sia comprensibile) e qual è il suo inverso moltiplicativo.
Essendo una diofantea del tipo $ax + by = c$, so che $mcd(a,b)$ deve dividere $c$ quindi è $1$ e il suo inverso moltiplicativo è dato dalla relazione stessa, cioè $568$. Cioè è già stato applicato l'Algoritmo di Euclide esteso.
Detto ciò, data una relazione del genere (cioè dato per certo che sia corretta) posso dire con certezza che con $c=1$ l'mcd tra tutti i numeri che ci sono sia 1? Quindi $ax + by = 1$, posso dire che $mcd(a,b)=mcd(x,y)=mcd(a,y)=mcd(b,x)=mcd(a,x)=mcd(by)=1$
Più che altro mi servirebbe una mano per capire come rispondere più correttamente e formalmente possibile.
Grazie in anticipo.
PS: Con = intendo congruo nel primo quesito ma non sapevo come scriverlo
Il primo mi chiede di dimostrare che n=91 non è primo applicando il Piccolo teorema di Fermat (senza fattorizzarlo).
Ho pensato:
Il PFT dice che, con n numero primo
$x^{n-1} = 1 mod n$
con $mcd(x,n)=1$
Con 91 sarebbe quindi: $x^90 = 1 mod 91$ con $mcd(x,91)=1$
Ecco, adesso come dimostro che quest'ultima congruenza non è vera senza dover fare calcoli spropositati?
Ad esempio con $x=2$, non dovrò mettermi a fattorizzare $2^90$ e moltiplicare le classi resto, dovrebbe esserci una "via" per dimostrarlo.
Per il secondo volevo chiedere più che altro una conferma:
Data la relazione:
$−173 · 371 + 113 · 568 = 1$
Dire se $x=113$ appartiene a (Z*371 non me lo scrive bene, spero sia comprensibile) e qual è il suo inverso moltiplicativo.
Essendo una diofantea del tipo $ax + by = c$, so che $mcd(a,b)$ deve dividere $c$ quindi è $1$ e il suo inverso moltiplicativo è dato dalla relazione stessa, cioè $568$. Cioè è già stato applicato l'Algoritmo di Euclide esteso.
Detto ciò, data una relazione del genere (cioè dato per certo che sia corretta) posso dire con certezza che con $c=1$ l'mcd tra tutti i numeri che ci sono sia 1? Quindi $ax + by = 1$, posso dire che $mcd(a,b)=mcd(x,y)=mcd(a,y)=mcd(b,x)=mcd(a,x)=mcd(by)=1$
Più che altro mi servirebbe una mano per capire come rispondere più correttamente e formalmente possibile.
Grazie in anticipo.
PS: Con = intendo congruo nel primo quesito ma non sapevo come scriverlo
Risposte
Ciao 
Per il punto 1): prova a calcolare l'ordine di $2$ in $\mathbb{Z}_91$.
Per il punto 2): credo sia corretto solo dire che $(a, b) = (x, y) = (a, y) = (b, x) = 1$(basta applicare Bezout). Per quanto riguarda $(a,x)$ e $(b, y)$ ho trovato un controesempio: $3x + 2y = 1$, se consideri $(3, -4)$ allora hai che $(3, 3) = 3$ e $(2, -4) = 2$ anche se $(3, 2) = 1$.
Per il punto 1): prova a calcolare l'ordine di $2$ in $\mathbb{Z}_91$.
Per il punto 2): credo sia corretto solo dire che $(a, b) = (x, y) = (a, y) = (b, x) = 1$(basta applicare Bezout). Per quanto riguarda $(a,x)$ e $(b, y)$ ho trovato un controesempio: $3x + 2y = 1$, se consideri $(3, -4)$ allora hai che $(3, 3) = 3$ e $(2, -4) = 2$ anche se $(3, 2) = 1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo