OliForum Matematico

Mi è venuto questo dubbio:
se a^k = 1 (mod b)
allora deve essere necessariamente
a = +-1 (mod b) ??????

$ 3^4 \equiv 1 \pmod5 $...

No, però sai che $ $a $ è coprimo con $ $b $ e che $ $k|\phi(b) $

ottimo grazie a tutti e due

julio14 ha scritto:No, però sai che $ $a $ è coprimo con $ $b $ e che $ $k|\phi(b) $

mmm, non proprio,sennò ce ne sarebbero finiti di k per cui vale quella cosa ,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.

Beh intanto grazie Carlein per queste utilissime precisazioni e buon anno anche a te

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 $

Non sono affatto esperto e spero di non dire cavolate
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?

Grazie Carlein, in effetti avevo detto le cose un bel po' male (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 )

trugruo 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?

E' giusto . 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).

Carlein 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.

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 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.

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.

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) $.
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).

grazie per la correzione si intendevo proprio quello e non sapevo avesse un nome XD
Comunque grazie davvero,tutto questo 3d mi è stato davero utile