n|2^{n-1}+1 [Ammissione wc]

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
Sesshoumaru
Messaggi: 87
Iscritto il: 13 dic 2007, 19:13
Località: Roma

Messaggio da Sesshoumaru » 15 gen 2008, 14:57

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:
[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]

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 17 gen 2008, 16:54

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

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 17 gen 2008, 17:06

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)

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 17 gen 2008, 17:14

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

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 17 gen 2008, 17:24

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: )

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 17 gen 2008, 17:36

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 $
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"

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 18 gen 2008, 14:15

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

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 18 gen 2008, 21:19

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:

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 19 gen 2008, 00:53

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

Rispondi