mn|3^m+1 e 3^n+1

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

mn|3^m+1 e 3^n+1

Messaggio da jordan » 09 mar 2010, 09:46

Trovare tutte le coppie di interi positivi m,n tali che il loro prodotto divide sia $ 3^m+1 $ che $ 3^n+1 $.
The only goal of science is the honor of the human spirit.

Dani92
Messaggi: 108
Iscritto il: 08 ott 2009, 18:32
Località: Trento

Re: mn|3^m+1 e 3^n+1

Messaggio da Dani92 » 09 mar 2010, 14:30

jordan ha scritto:Trovare tutte le coppie di interi positivi m,n tali che il loro prodotto divide sia $ 3^m+1 $ che $ 3^n+1 $.
$ mn|3^m+1 $
$ mn|3^n+1 $

Osservo che ne m ne n può essere divisibile per 3 perchè $ 3^k+1 $ non è divisibile per 3

Pongo WLOG $ m \geqslant n $ e deve succedere che $ mn|3^m-3^n $

Però allora, perchè questo numero non sia divisibile per 3, ho due opzioni:

A) n=0 --> impossibile poi verificare l'ipotesi
B) n=m, lo sostituisco ed ho che

$ m^2|3^m+1 $
Osservo che m dev'essere pari oppure 1, per parità dei due termini. Però se è pari allora
$ 3^m+1 \equiv 2 (mod4) $ ma i residui quadratici di mod 4 sono solo 0 e 1, ed è quindi impossibile.

L'unica soluzione accettabile è quindi m=n=1 che effettivamente verifica l'ipotesi.

E' corretto? :D

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

Messaggio da cromat » 09 mar 2010, 16:50

L'unica soluzione accettabile è quindi m=n=1 che effettivamente verifica l'ipotesi.
a prima occhiata direi che anche (1,2) va bene

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Re: mn|3^m+1 e 3^n+1

Messaggio da ndp15 » 09 mar 2010, 17:30

Dani92 ha scritto: Però allora, perchè questo numero non sia divisibile per 3, ho due opzioni:
Perchè non puo' essere divisibile per 3?

Dani92
Messaggi: 108
Iscritto il: 08 ott 2009, 18:32
Località: Trento

Messaggio da Dani92 » 09 mar 2010, 20:18

Si ho detto una cagata gigantesca... :shock:

Avatar utente
Francutio
Messaggi: 1104
Iscritto il: 17 feb 2008, 08:05
Località: Torino

Re: mn|3^m+1 e 3^n+1

Messaggio da Francutio » 10 mar 2010, 16:17

Probabilmente non ci azzecca assolutamente niente con il problema, ma tirando a caso combinazioni a scuola mi sono chiesto: questi passaggi sono validi?



$ m^2n^2 | 3^2m+2*3^m+1 $

$ m^2n^2 -mn | 3^2m+3^m $

$ mn(mn-1) | 3^m(3^m+1) $

$ (mn-1) | 3^m $


Probabilmente no, in ogni caso potreste sempre insegnarmi come mettere il (2m) tutto all'esponente... :oops:

Avatar utente
gismondo
Messaggi: 84
Iscritto il: 05 feb 2009, 18:42
Località: Roma

Messaggio da gismondo » 10 mar 2010, 17:03

x^{2m}
$ x^{2m} $
in ogni caso 25|2500 e 5|50 ma 20 non divide 2450...
"Per tre cose vale la pena di vivere: la matematica, la musica e l'amore"

Avatar utente
Francutio
Messaggi: 1104
Iscritto il: 17 feb 2008, 08:05
Località: Torino

Messaggio da Francutio » 11 mar 2010, 16:22

gismondo ha scritto:x^{2m}
$ x^{2m} $
in ogni caso 25|2500 e 5|50 ma 20 non divide 2450...

Ecco...lo sapevo che sparavo una *******

Almeno ho imparato a mettere gli esponenti...grazie ^^

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 31 mar 2010, 16:55

m e n non possono essere entrambi pari. Se così fosse, $ \displaystyle~4\mid mn\mid 3^m+1 $, ma $ \displaystyle~3^m+1\equiv (-1)^m+1\equiv 2\pmod 4 $. Dunque posto $ \displaystyle~x=(m,n) $ abbiamo x dispari.
Dall'ipotesi $ \displaystyle~mn\mid 3^m+1\mid 9^m-1 $ e $ \displaystyle~mn\mid 3^n+1\mid 9^n-1 $. Toh, proprio 10 mesi fa era capitato sul forum un lemma che ci permette di dire che $ \displaystyle~mn\mid 9^x-1 $, da cui otteniamo l'ipotesi più debole $ \displaystyle~x^2\mid 9^x-1 $.
Supponiamo $ \displaystyle~x>1 $ e sia $ \displaystyle~x=p_1^{e_1}\cdots p_u^{e_u} $ la fattorizzazione di x con $ \displaystyle~p_i<p_j~\forall i<j $.
Deve valere $ \displaystyle~p_1^{2e_1}\mid 9^{p_1^{e_1}\cdots p_u^{e_u}}-1~(*) $, in particolare $ \displaystyle~p_1\mid 9^{p_1^{e_1}\cdots p_u^{e_u}}-1 $ o applicando ripetutamente il piccolo teorema di Fermà $ \displaystyle~p_1\mid 9^{p_2^{e_2}\cdots p_u^{e_u}}-1 $
Dunque possiamo applicare quest'altro lemma che insieme alla $ \displaystyle~(*) $ dà
$ \displaystyle~\upsilon_{p_1}((9^{p_2^{e_2}\cdots p_u^{e_u}})^{p_1^{e_1}}-1)=\upsilon_{p_1}(9^{p_2^{e_2}\cdots p_u^{e_u}}-1)+\upsilon_{p_1}(p_1^{e_1})\ge 2e_1 $ cioè $ \displaystyle~\upsilon_{p_1}(9^{p_2^{e_2}\cdots p_u^{e_u}}-1)\ge e_1 $.
Da $ \displaystyle~9^{p_2^{e_2}\cdots p_u^{e_u}}\equiv 1\pmod {p_1^{e_1}} $ abbiamo $ \displaystyle~ord_{p_1^{e_1}}(9)\mid (p_2^{e_2}\cdots p_u^{e_u},p_1^{e_1-1}(p_1-1))=(p_2^{e_2}\cdots p_u^{e_u},p_1-1)=1 $, infatti $ \displaystyle~p_1-1<p_i~\forall i $ quindi $ \displaystyle~p_1-1 $ non è divisibile per nessun $ \displaystyle~p_i $. Per cui $ \displaystyle~p_1^{e_1}\mid 9-1=8 $, assurdo.
Segue che $ \displaystyle~x=1 $, cioè $ \displaystyle~mn\mid 9-1=8 $, quindi (1,1), (1,2) e (2,1) sono le uniche soluzioni.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 31 mar 2010, 17:05

Perfetto :)
Oramai almeno quei due lemmi dovrebbero essere dati per noti :wink:
The only goal of science is the honor of the human spirit.

Rispondi