primi e potenze di 2 - di provenienza francese

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

primi e potenze di 2 - di provenienza francese

Messaggio da piever » 05 dic 2008, 16:04

Per niente scoraggiato dal fatto i miei thread in TdN abbiano in media 0 risposte, vi propongo un altro simpatico problemino:

dimostrare che esistono infinite coppie di primi distinti p e q tali che:

$ 2^p\equiv 2^q \pmod{pq} $

Buon lavoro!
"Sei la Barbara della situazione!" (Tap)

Erre
Messaggi: 11
Iscritto il: 03 dic 2008, 20:50

Messaggio da Erre » 05 dic 2008, 18:24

scusa sono un po fuori dal giro dei simbolismi avanzati....
ma che vuol dire quel uguale a tre linee?

ciao
Chi dorme non piglia pesci,
....ma gelato, torta e caffe.

/garfield/

Jack Luminous
Messaggi: 42
Iscritto il: 06 nov 2008, 20:57

Messaggio da Jack Luminous » 05 dic 2008, 18:32

Vuol dire che quei due numeri sono congrui tra loro modulo pq, ossia che danno lo stesso resto nella divisione per pq :wink:

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 11 dic 2008, 15:24

piever ha scritto:Per niente scoraggiato dal fatto i miei thread in TdN abbiano in media 0 risposte, vi propongo un altro simpatico problemino:
per provare a movimentare un pò il tuo thread in nome di una vecchia conoscenza provo a buttare giù una bozza di risposta (anche senza latex :oops: )

prendiamo p>q (q>p è un caso simmetrico)
1) 2^p è congruo a 2^q (mod p)
2) 2^p è congruo a 2^q (mod q) ----> teorema cinese

2^p é congruo a 2 (mod p)
2^q è congruo a 2 (mod q) (fermat)
per la 2) ----> 2^p è congruo a 2(mod q) ----> 2^p= kq+2 (con k intero positivo)
per la 1) ----> kq+2 è congruo a 2(mod p) ----> kq congruo a 0 (mod p)---->
k,q (entrambi interi positivi) dividono p ----> p non è primo


ora fatevi avanti con le correzioni e scusate per il modo in cui è scritto :?

Avatar utente
LeopoldoXII
Messaggi: 73
Iscritto il: 01 mag 2006, 15:01
Località: Molfetta (BA)

Messaggio da LeopoldoXII » 12 dic 2008, 17:47

ops
Ode all'EATODE

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 12 dic 2008, 18:31

cromat ha scritto:per provare a movimentare un pò il tuo thread in nome di una vecchia conoscenza provo a buttare giù una bozza di risposta
Sono commosso :D

Però vorrei farti dimostrare che la dimostrazione, oltre ad avere alcuni passaggi la cui validità è discutibile, non dimostra la tesi ma qualcos'altro (cioè "p non è primo") che, per inciso, è falso.
LeopoldoXII ha scritto:ops
Anche questo è un approccio molto interessante al problema... Un altro lemmino utile per trovare la soluzione potrebbe essere "Non ho toccato nulla! Era già tutto così quando sono arrivato!" :P

Tra l'altro, prima che io scrivessi questo messaggio, avevi la possibilità di cancellare il tuo post... :?

Se invece hai scritto un post del tutto inutile solo per sfoggiare la firma, allora hai fatto benissimo :D
Ultima modifica di piever il 12 dic 2008, 18:33, modificato 1 volta in totale.
"Sei la Barbara della situazione!" (Tap)

Avatar utente
LeopoldoXII
Messaggi: 73
Iscritto il: 01 mag 2006, 15:01
Località: Molfetta (BA)

Messaggio da LeopoldoXII » 12 dic 2008, 18:32

Spero tu non me ne voglia se provo ad alzare la tua media del numero di risposte.

Grazie ai miei elevati strumenti di calcolo ho trovato come soluzione $ $(11,31)$ $, che probabilmente è la più piccola.
Ora, data una soluzione $ $(p,q)$ $, ne cerchiamo una $ $(s,t)$ $ più grande nel senso che $ $min\{p,q\}<min\{s,t}$ $.

Se $ $2^p-1=s$ $ e $ $2^q-1=t$ $ sono entrambi primi, allora essi formano una soluzione. Infatti
$ $2^{s}\equiv 2 \pmod{s}$ $. Poichè $ $p=ord_s(2)$ $ e $ $p|2(2^{q-1}-1)$ $ allora
$ $2^{t}\equiv 2 \equiv 2^{s} \pmod{s}$ $ e in modo simmetrico
$ $2^{t}\equiv 2^{s} \pmod{t}$ $. Per il teorema cinese vale la tesi.

Se invece non sono entrambi primi esistono due primi s e t che dividono wlog $ $2^p-1$ $. Allora $ $ord_s(2),ord_t(2)|p$ $ e poichè p è primo $ $ord_s(2),ord_t(2)=p$ $,
per Fermat $ $t\equiv s\equiv 1 \pmod{p}$ $
e quindi $ $2^{t}\equiv 2^{s} \pmod{st}$ $.


Mentre scrivo mi sono accorto che manca il caso che $ $2^p-1=r^n$ $ dove r è un primo. Ma cio è impossibile perchè:
Se n è pari, allora $ $2^p-2=r^n-1$ $ e 4 divide il RHS ma non il LHS.
Se n è dispari $ $2^p=(r+1)(r^{n-1}-r^{n-2}+\ldots+1) $ ma il secondo fattore del RHS è sempre dispari.
Ultima modifica di LeopoldoXII il 13 dic 2008, 17:45, modificato 1 volta in totale.
Ode all'EATODE

Avatar utente
LeopoldoXII
Messaggi: 73
Iscritto il: 01 mag 2006, 15:01
Località: Molfetta (BA)

Messaggio da LeopoldoXII » 12 dic 2008, 18:35

piever ha scritto: Anche questo è un approccio molto interessante al problema... Un altro lemmino utile per trovare la soluzione potrebbe essere "Non ho toccato nulla! Era già tutto così quando sono arrivato!" :P

Tra l'altro, prima che io scrivessi questo messaggio, avevi la possibilità di cancellare il tuo post... :?

Se invece hai scritto un post del tutto inutile solo per sfoggiare la firma, allora hai fatto benissimo :D
Piuttosto ero intento nel modificarlo, ma non so perchè, anche questo tentativo è risultato vano. :roll:
Ode all'EATODE

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 12 dic 2008, 18:52

Uhm, fidandomi del fatto che $ 11\cdot 31 |(2^{31}-2^{11}) $ (cosa che i miei mezzi di calcolo non sono sufficientemente potenti per verificare) direi che la tua soluzione funziona e che ora in media gli n problemi che ho postato su forum hanno 1/n soluzioni!!! :D :D :D

Tra l'altro è molto più elegante della pseudosoluzione che avevo dato io al simpaticissimo francesino (Sergio) che mi aveva proposto questo problema... Poi magari gli do un link a questa pagina.. Per caso sai se si trovano dizionari dal molfettese al francese on-line?

Per escludere il caso $ 2^p-1=r^n $ (con n>1, che non necessariamente coincide con il numero di problemi che ho postato su forum) l'onnipotente Mihailescu non dovrebbe essere indispensabile :P Cmq ti capisco, in momenti di stanchezza estrema ho fatto cose peggiori (le mie soluzioni pullulano di "si vede facilmente che.." :wink: )...
"Sei la Barbara della situazione!" (Tap)

Rispondi