Si, infattisalva90 ha scritto:eccone un altroPigkappa 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...
n|2^{n-1}+1 [Ammissione wc]
-
Sesshoumaru
- Messaggi: 87
- Iscritto il: 13 dic 2007, 19:13
- Località: Roma
[img]http://img65.imageshack.us/img65/2554/userbar459811cf0.gif[/img]
[i]"You have a problem with your brain: the left part has nothing right in it, and the right part has nothing left in it."[/i]
[i]"You have a problem with your brain: the left part has nothing right in it, and the right part has nothing left in it."[/i]
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?
$ 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?
Ultima modifica di Carlein il 18 gen 2008, 14:20, modificato 1 volta in totale.
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"
O mi sono persa qualcosa o te stai dicendo che :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.
$ 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)
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
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
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"
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 $
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 $
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"
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.
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.
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"
Questa è l'unica parte veramente oscura della soluzione.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.
Ciònonostante, stai sfiorando la soluzione di un problema che riguarda gli ordini moltiplicativi, inventandoti il concetto di ordine moltiplicativo, veramente complimenti!!
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..
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..
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"