primi e potenze di 2 - di provenienza francese

[piever]

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!

[Erre]

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

ciao

[Jack Luminous]

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

[cromat]

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 )

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

[LeopoldoXII]

ops

[piever]

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

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.

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

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

[LeopoldoXII]

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.

[LeopoldoXII]

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

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

Piuttosto ero intento nel modificarlo, ma non so perchè, anche questo tentativo è risultato vano.

[piever]

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

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 Cmq ti capisco, in momenti di stanchezza estrema ho fatto cose peggiori (le mie soluzioni pullulano di "si vede facilmente che.." )...