Pagina 2 di 2

Inviato: 15 gen 2008, 14:57
da Sesshoumaru
salva90 ha scritto:
Pigkappa ha scritto:Ah, il caro vecchio metodo di fare i conti a caso e di fretta, sbagliandoli, trovando perciò un assurdo e risolvendo così il problema...
eccone un altro :lol:
Si, infatti :lol:

Inviato: 17 gen 2008, 16:54
da Carlein
ho provato a farlo ieri ma mi sono bloccato in un punto;vorrei chiedervi se mi trovo proprio in un vicolo cieco,oppure se si arriva da qualche parte:
$ 2^{2(n-1)} \equiv 1 \pmod n $ dunque col piccolo di Fermat possiamo distinguere due casi,rispetto ad un generico fattore primo di n che chiamiamo a:2(n-1) è multiplo di (a-1),oppure 2(n-1) è multiplo di uno dei sottomultipli di (a-1).Questa seconda cosa l'ho notata solo ieri,ma ha carattere generale;primo caso:
$ 2(n-1) \equiv 0 \pmod {a-1} $ che implica $ n \equiv 1 \pmod {a-1} $ che implica $ 2^{n-1} \equiv -1 \pmod a $ e $ 2^{n-1} \equiv 1\pmod a $ dunque a sarebbe 2 e i suoi multipli dispari,assurdo.Il secondo caso è un fattarello che forse è noto e banale ma io ne ero all'oscuro:si può dimostrare così ,si ponga il minimo numero k minore di (a-1) ma tale che valga quello che si diceva;poniamo per assurdo che k non sia sottomultiplo di (a-1);esiste un kc avente un residuo modulo(a-1) minore di k ma per il quale vale la tesi,cosa che non può succedere quando è sottomultiplo,il che contraddice che il minimo per cui valeva la tesi era k.Dimostrato che il minimo per cui vale deve essere sottomultiplo di (a-1) è immediato dimostrare(si fa in maniera eguale alla prima)che solo i multipli di k rendono valida la tesi (tra cui a-1).Detto questo ora non vedo molto come attaccare questa seconda cosa:dunque riparto da 0 oppure vi è un assurdo banale anche in questo secondo caso?

Inviato: 17 gen 2008, 17:06
da EUCLA
Carlein ha scritto: $ 2(n-1) \equiv 0 \pmod {a-1} $ che implica $ n \equiv 1 \pmod {a-1} $ che implica $ 2^{n-1} \equiv -1 \pmod a $ e $ 2^{n-1} \equiv 1\pmod a $ dunque a sarebbe 2 e i suoi multipli dispari,assurdo.
O mi sono persa qualcosa o te stai dicendo che :

$ 2^{2(n-1)}\equiv 1 \pmod a \Rightarrow 2^{n-1}\equiv 1 \pmod a $ e $ 2^{n-1}\equiv -1 \pmod a $ che è un'implicazione falsa in quanto basta che sia verificata una sola delle due disuguaglianze ottenute affinchè $ 2^{2(n-1)}\equiv 1 \pmod a $.

(Non ho ancora letto la seconda parte)

Inviato: 17 gen 2008, 17:14
da Carlein
mi sa che hai perso un passaggio:io ho detto che $ (n-1) \equiv 0 \pmod (a-1) $ che implica ,per fermat, $ 2^{n-1} \equiv 1 \pmod a $,metti questo affianco all'ipotesi del problema e hai che a deve essere necessariamente 2, e i suoi multipli dispari.
La seconda parte la illustro con un esempio,nel caso non sia stato chiaro.$ 2^3 \equiv 1 \pmod 7 $ e 3 è sottomultiplo di 6

Inviato: 17 gen 2008, 17:24
da EUCLA
Ok! Mi ero completamente dimenticata delle ipotesi del problema, che stava nell'altra pagina e cercavo di trovare dei passaggi logici.

(La seconda non è che non mi è chiara, non mi ci sono proprio messa perchè ho un pò da fare ora :wink: )

Inviato: 17 gen 2008, 17:36
da Carlein
la seconda l'ho scritta coi piedi scusate,ma sta chiudendo il quadrimestre e.... :?
Comunque il teoremetto che asserisco e dimostro è questo:se a è primo ,n e f interi positivi tali che $ n^f \equiv 1 \pmod a $ allora o $ f \equiv 0 \pmod {a-1} $ (Fermat) o f è multiplo di un sottomultiplo k di (a-1) per cui vale $ n^k \equiv 1 \pmod a $

Inviato: 18 gen 2008, 14:15
da Carlein
ieri,frastornato dalla giornataccia nn mi sono accorto che avevo la soluzione sotto il naso:per amor di estetica scriverò la soluzione integralmente,per non costringere i lettori a fare avani e indietro per i post.
L'ipotesi implica:
$ 2^{2(n-1)} \equiv 1 \pmod a $ dove a è un fattore primo di n.
Questo implica due possibilità: $ 2(n-1) \equiv 0 \pmod {a-1} $,oppure
$ 2(n-1) \equiv 0 \pmod k $ dove k è un sottomultiplo di (a-1),per cui vale $ 2^k \equiv 1 \pmod a $.il fatto che siano le sole alternative possibili l'ho dimostrato prima(questo non lo riporto se no faccio un romanzo).
La prima implica che:$ (n-1) \equiv 0 \pmod {a-1} $ che implica $ 2^{n-1} \equiv 1 \pmod a $ e $ 2^{n-1} \equiv -1 \pmod a $,che significa che a è 2 e i suoi multipli dispari.
Secondo caso:per ciascun fattore primo di n (chiamiamoli $ a_1,a_2... $)
deve esistere un $ k_m $ per cui $ (a_m-1) \equiv 0 \pmod k_m $ e per cui $ 2(n-1) \equiv 0 \pmod k_m $ se i vari k fossero diversi tra loro si avrebbe che $ 2(n-1) \equiv 0 \pmod {k_m} $ per almeno un valore di k implica$ (n-1) \equiv 0 \pmod {k_m} $ che porta allo stesso assurdo del primo caso. Dunque abbiamo che tutti i valori di k devono essere eguali tra loro. Ma poichè $ (a_m-1) \equiv 0 \pmod k $ si ha operando coi moduli che $ (n-1) \equiv 0 \pmod k $ che ci porta al solito assurdo.
fine.

Inviato: 18 gen 2008, 21:19
da edriv
Carlein ha scritto:ieri,frastornato dalla giornataccia nn mi sono accorto che avevo la soluzione sotto il naso:per amor di estetica scriverò la soluzione integralmente,per non costringere i lettori a fare avani e indietro per i post.
L'ipotesi implica:
$ 2^{2(n-1)} \equiv 1 \pmod a $ dove a è un fattore primo di n.
Questo implica due possibilità: $ 2(n-1) \equiv 0 \pmod {a-1} $,oppure
$ 2(n-1) \equiv 0 \pmod k $ dove k è un sottomultiplo di (a-1),per cui vale $ 2^k \equiv 1 \pmod a $.il fatto che siano le sole alternative possibili l'ho dimostrato prima(questo non lo riporto se no faccio un romanzo).
La prima implica che:$ (n-1) \equiv 0 \pmod {a-1} $ che implica $ 2^{n-1} \equiv 1 \pmod a $ e $ 2^{n-1} \equiv -1 \pmod a $,che significa che a è 2 e i suoi multipli dispari.
Secondo caso:per ciascun fattore primo di n (chiamiamoli $ a_1,a_2... $)
deve esistere un $ k_m $ per cui $ (a_m-1) \equiv 0 \pmod k_m $ e per cui $ 2(n-1) \equiv 0 \pmod k_m $ se i vari k fossero diversi tra loro si avrebbe che $ 2(n-1) \equiv 0 \pmod {k_m} $ per almeno un valore di k implica$ (n-1) \equiv 0 \pmod {k_m} $ che porta allo stesso assurdo del primo caso. Dunque abbiamo che tutti i valori di k devono essere eguali tra loro. Ma poichè $ (a_m-1) \equiv 0 \pmod k $ si ha operando coi moduli che $ (n-1) \equiv 0 \pmod k $ che ci porta al solito assurdo.
fine.
Questa è l'unica parte veramente oscura della soluzione.

Ciònonostante, stai sfiorando la soluzione di un problema che riguarda gli ordini moltiplicativi, inventandoti il concetto di ordine moltiplicativo, veramente complimenti!! :wink:

Inviato: 19 gen 2008, 00:53
da Carlein
Edriv hai ragione in quel passaggio sono stato sibillino;avevo errato in un calcolo di moduli e questo mi ha portato alla suddivisione in quei due casi che alla luce della riflssione successiva(quella di qui sotto ) si rivela inutile.
vogliamo che per ogni $ a_m $ il relativo $ k_m $ sia tale che $ 2(n-1) \equiv 0 \pmod {k_m} $ ,ma $ (n-1) \equiv {k_m/2} \pmod k_m $, perchè se invece $ (n-1) \equiv 0 \pmod {k_m} $ si ha lo stesso assurdo del primo caso(per capire questo basta applicare la definizione che abbiamo dato di k_m .Ora perchè questa congruenza sia vera deve essere che tutti i valori di $ k_m $ siano pari e in ciascuno di essi 2 abbia lo stesso esponente f;sennò per evidenti ragioni di m.c.m. si arriva per almeno uno dei fattori primi a quell'assurdo di prima.Ora è facile vedere che $ a_1a_2...a_m=n \equiv 1 \pmod {2^f} $ che implica falsa la congruenza $ (n-1) \equiv k_m/2 \pmod k_m $ che implica che se è vera l'ipotesi ovvero $ 2(n-1) \equiv 0 \pmod {k_m} $ allora deve essere vera anche questa $ (n-1) \equiv 0 \pmod {k_m} $ che sappiamo bene essere un assurdo. Così risulta superflua quella suddivisione che avevo precedentemente fatto su $ k_m $ e il secondo caso dovrebbe essere veramente chiuso.
p.s.:se non avessi il cervello semifuso della soluzione notturna,mi sarei andato a vedere subito cos'è un ordine moltiplicativo,ma mi sa che lo farò domani...mi hai messo una curiosità addosso.. :D :D