Mi è venuto questo dubbio:
se a^k = 1 (mod b)
allora deve essere necessariamente
a = +-1 (mod b) ??????
Dubbio banale su congruenze....
mmm, non proprio,sennò ce ne sarebbero finiti di k per cui vale quella cosajulio14 ha scritto:No, però sai che $ $a $ è coprimo con $ $b $ e che $ $k|\phi(b) $
,neanche se ti restringi a quelli minori di phi(b)vale: $ 2^{25} \equiv 1 \pmod{31} $.Ok scherzi a parte,julio penso lui intendesse un k qualunque per cui vale la relazione;quello che julio aveva in mente di comunicarti penso fosse: il più piccolo m>0 per cui $ a^m \equiv 1 \pmod b $ divide phi(b), più in generale divide tutti i k t.c $ a^k \equiv 1 \pmod b $(nell'esempio di prima m=5;quindi se hai 2^k=1mod31 potresti dire che k è multiplo di 5;comunque trugruo prova a capire il perchè di questa cosa, può esserti un utile esercizio).Buon anno gente
p.s: anzi trugruo, visto che ci sei,poichè di sicuro ignori il teorema di eulero-fermat altrimenti avresti trovato subito modo di autoconfutarti, prova a dimostrare per esercizio che se a è coprimo con b esiste un N>0 per cui $ a^N \equiv 1 \pmod b $,ossia autoconfutati in modo elementare,dopodichè chiarisciti che tutti i multipli di N fanno questa cosa(che è un motivo per cui non potevi avere la cosa che citavo su) dopodichè provati a pigliare il minimo e vedi che succede quando fai i suoi i multipli e se ci fosse qualcuno che non becca(cioè fatti l'esercizio che ti consigliavo su)poi: il teorema che dicevo prima ti dice che uno di questi N è phi(b)(ossia il numero di resti modulo b coprimi con b), ma prima provati a fare queste cose più in astratto(ossia senza individuare numeri precisi che fanno sto servizio,ma vedendo che in ogni caso ci devono essere),il che è in effetti un pò più facile, dopodichè qui sul glossario trovi dimostrazioni carine e elementari del teorema.
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Beh intanto grazie Carlein per queste utilissime precisazioni e buon anno anche a te 
pensavo di poterlo dimostrare così:
considerando che i resti modulo b sono b-1 quindi sono in numero finito,
prima o poi avremo due interi c e d con c > d tali che
a^c = a^d (mod b)
dividendo tutto per a^d che è la potenza minore (posso farlo in quanto a e b sono coprimi)
si ottiene a^(c-d) = 1 (mod b)
quindi N=c-d
E' plausibile o ho scritto solo baggianate?
Non sono affatto esperto e spero di non dire cavolatep.s: anzi trugruo, visto che ci sei,poichè di sicuro ignori il teorema di eulero-fermat altrimenti avresti trovato subito modo di autoconfutarti, prova a dimostrare per esercizio che se a è coprimo con b esiste un N>0 per cui $ a^N \equiv 1 \pmod b $
pensavo di poterlo dimostrare così:
considerando che i resti modulo b sono b-1 quindi sono in numero finito,
prima o poi avremo due interi c e d con c > d tali che
a^c = a^d (mod b)
dividendo tutto per a^d che è la potenza minore (posso farlo in quanto a e b sono coprimi)
si ottiene a^(c-d) = 1 (mod b)
quindi N=c-d
E' plausibile o ho scritto solo baggianate?
(per come l'avevo messa io, era proprio sbagliata 
è che pensavo in $ $\mathbb{Z}_{\phi (b) $, e il divide era diventato "è zero-divisore", escluso a=1 E' giustotrugruo ha scritto:
considerando che i resti modulo b sono b-1 quindi sono in numero finito,
prima o poi avremo due interi c e d con c > d tali che
a^c = a^d (mod b)
dividendo tutto per a^d che è la potenza minore (posso farlo in quanto a e b sono coprimi)
si ottiene a^(c-d) = 1 (mod b)
quindi N=c-d
E' plausibile o ho scritto solo baggianate?
. Così già hai dato una risposta a quanto chiedevi a inizio 3d:esistendo per ogni a coprimo con b un tale N, non potrai escludere a priori tutti quelli diversi da + o-1,dalla relazione che dicevi tu,anzi. Ora fissato a coprimo con b, tu hai dimostrato che l'insieme degli N naturali t.c $ a^N \equiv 1 \pmod b $ non è vuoto. Da qui riesci facilmente a dire che è infinito $ a^N \equiv 1 \pmod b $ implica $ a^{hN} \equiv 1 \pmod b $ per ogni h nei naturali. Ecco ora su questo tipo di constatazioni se ne può fare un'altra che ti dice come è fatto questo insieme: se ti va prova a capire la seconda cosa che ti dicevo;ossia prova a vedere che succede quando prendi il minimo di quest'insieme(che chiaramente esiste) e capire perchè i suoi multipli sono tutti e soli gli elementi di quest'insieme(se all'inizio non riesci a vedere niente in generale prova a vedere a mano sull'esempio che si faceva prima: $ 2^5 \equiv 1 \pmod {31} $ e 5 è il minimo per cui succede, perchè non si potrà avere $ 2^7 \equiv 1 \pmod{31} $? come lo puoi capire subito dal fatto che $ 2^5 \equiv 1 \pmod {31} $? poi generalizzare sarà facile).Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
se chiamiamo A l'insieme degli esponenti che soddisfano la condizione ed m il suo minimo,abbiamo visto cheCarlein ha scritto: Ecco ora su questo tipo di constatazioni se ne può fare un'altra che ti dice come è fatto questo insieme: se ti va prova a capire la seconda cosa che ti dicevo;ossia prova a vedere che succede quando prendi il minimo di quest'insieme(che chiaramente esiste) e capire perchè i suoi multipli sono tutti e soli gli elementi di quest'insieme.
h*m appartiene ancora all'insieme,inoltre è chiaro che la differenza fra ogni elemento dell'insieme sta ancora in A.
Ma se per assurdo supponiamo che esista un elemento n>m non multiplo di m,allora appartiene all'insieme A anche l'elemento (n mod m) che è minore di m,assurdo visto che m era il minimo dell'insieme.
Ultima modifica di trugruo il 02 gen 2010, 19:48, modificato 1 volta in totale.
Penso che hai capito;una domanda: nella frase sottolineata intendevi "la differenza tra ogni 2 elementi in A, sta ancora... in A"? Magari chiariscilo perchè non si capisce, in italiano, cosa stai dicendo. Dal punto di vista del significato, col resto delle cose che dici, penso intendevi questo; quindi si è tutto giusto. Questo m lo si chiama ordine moltiplicativo di a rispetto a b, e lo si indica con $ ord_b(a) $.trugruo ha scritto: se chiamiamo A l'insieme degli esponenti che soddisfano la condizione ed m il suo minimo,abbiamo visto che
h*m appartiene ancora all'insieme,inoltre è chiaro che la differenza fra ogni elemento dell'insieme deve essere pari ad m.
Ma se per assurdo supponiamo che esista un elemento n>m non multiplo di m,allora appartiene all'insieme A anche l'elemento (n mod m) che è minore di m,assurdo visto che m era il minimo dell'insieme.
Ora tanto per chiudere riguardo alle cose che ti può servire sapere riguardo alla domanda iniziale che ponevi è il teorema di eulero fermat(o meglio, un'altra cosa collegata alle cose che penso ignoravi fino a oggi a causa della domanda iniziale): dice che sempre con a e b coprimi $ a^{\phi(b)} \equiv 1 \pmod b $ dove $ \phi(b) $ indica il numero di naturali minori di b,coprimi con b.Ed è quello con cui gauss 91 ti ha dato un controesempio. Una relazione che spesso capita di poter usare nei problemi è $ ord_b(a)|\phi(b) $ che deriva dalla proprietà che hai appena visto e questo teorema insieme.
p.s: se cerchi in questa sezione il teorema, trovi almeno un paio di 3d in cui se ne parla e con alcune dimostrazioni(alcune sono davvero belle).
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"