41 Cattivo!

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
ikkio
Messaggi: 5
Iscritto il: 03 mag 2006, 12:44

41 Cattivo!

Messaggio da ikkio »

Ciao a tutti, sono nuovo, partecipo alle olimpiadi da qualche anno, ma l'anno scorso per la prima volta più o meno decentemente fino a cesenatico (squadre) e consulto il forum da un pò, senza capirci troppo, a dirla tutta :( Sperando di non aver ancora infranto alcuna regola del forum (che leggerò quando sarò meno :twisted: :evil: !! ), chido subito le presentazioni e passo a proporvi un problema del SNS 94/95 che non riesco nemmeno a iniziare (scusate se ora vien fuori che è uno di quelli risolti nel 1000 a.C)

Mostrare che 41 non può essere espresso come differenza di una potenza di 2 e di una potenza di 3, cioè che non può sussistere nessuna delle due uguaglianze seguenti:
$ 41=2^n-3^m $; $ 41=3^n-2^m $, con n, m interi positivi.

Ah pleeeease...siate buoni con me, non spariamo i paroloni difficili che di teoria dei numeri non ho kapito un beeeep! (la mia "bibbia" fin ora sono state le schede olimpiche del 2003...anzi, a proposito, se avete qualcosa da consigliarmi...) Spero che vedendo risolto un problema su cui ho pensato, magari comincio a risolverne anche io qualcuno, chissà. Graaazie 3000 :lol:

(cmq...chiedo scusa per dove l'ho messo, ma me ne sono accorto dopo che era il posto sbagliato, non sono riuscito a spostarlo :oops:) PS. L'ho spostato, grazie a skZ!
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Re: 41 Cattivo!

Messaggio da HiTLeuLeR »

ikkio ha scritto: Mostrare che 41 non può essere espresso come differenza di una potenza di 2 e di una potenza di 3, cioè che non può sussistere nessuna delle due uguaglianze seguenti:
$ 41=2^n-3^m $; $ 41=3^n-2^m $, con n, m interi positivi.
Innanzitutto osserva che la congruenza $ 3^m \equiv \pm 7\bmod 2^n $ non ammette soluzioni per $ m\in\mathbb{N} $, se $ n $ è un intero $ \ge 4 $. Questo segue immediatamente dalla considerazione che - sotto le ipotesi dette - l'ordine moltiplicativo di $ 2^n $ alla base 3 è pari a $ 2^{n-2} $. Perciò gli unici residui $ r $ compatibili con l'equazione $ 3^m \equiv r \bmod 2^4 $ appartengono necessariamente all'insieme $ \{1, 3, 3^2, 3^3\} $, e nessuno fra questi eguaglia $ \pm 7 $ modulo $ 2^4 $. Restano i casi $ n = 1, 2, 3 $, di cui però non dico, visto che serve davvero un nulla per accomodarseli a manina.

EDIT: un $ n $ al posto di un 4 all'esponente di un modulo.
Ultima modifica di HiTLeuLeR il 12 dic 2006, 09:59, modificato 2 volte in totale.
Avatar utente
Ponnamperuma
Messaggi: 411
Iscritto il: 10 lug 2006, 11:47
Località: Torino

Messaggio da Ponnamperuma »

Vorrei postare una dimostrazione dell'irresolubilità di $ 41=2^n-3^m $, che mi sembra più semplice di quella di Hitleuler, se non altro perché non fa uso di concetti più avanzati delle congruenze (e con questo, ovviamente, nulla tolgo alla prima soluzione! :wink:). Per il secondo caso work in progress... Comunque
$ 41\equiv 1 \pmod8 $, mentre $ 2^n \equiv 0 \pmod8, n>2 $, per i casi $ n=1,n=2 $ si vede a mano che non ci sono soluzioni.
Riscrivo l'equazione come $ 41-2^n=-3^m $: il primo membro è $ \equiv 1 \pmod8 $, voglio dunque vedere se il secondo lo è parimenti, ovvero voglio vedere se $ 3^m \equiv -1 \pmod8 $. Ovviamente, se non lo fosse, avrei finito.
Noto che $ 3^2 \equiv 1 \pmod8 $ e distinguo i casi di m pari e dispari.
Se m è pari, scrivo $ 3^m=(3^2)^h \equiv 1 \pmod8 $, altrimenti ho $ 3^m=3(3^2)^k \equiv 3 \pmod8 $, con h,k interi positivi anch'essi.
Poichè in nessuno dei due casi ottengo una congruenza a -1 mod 8, concludo che l'equazione è priva di soluzioni.

Ciao! :D
La grandezza dell'uomo si misura in base a quel che cerca e all'insistenza con cui egli resta alla ricerca. - Martin Heidegger

MIND torna!! :D
ikkio
Messaggi: 5
Iscritto il: 03 mag 2006, 12:44

..domande stupide..

Messaggio da ikkio »

...foooorte!
Quella di Ponnamperuma l'ho capita tutta :D , solo una domandina: c'era qualche indizio che suggerisse proprio il modulo 8? partendo da lì, forse ci sarei arrivato... (ho provato anche un metodo analogo per il secondo caso, ma sembra niente da fare)
Tra l'altro, per come è dimostrata, in pratica dovrebbe funzionare per qualsiasi $ k \equiv1 \pmod8 $ al posto di 41!! ( :? giusto?)
Sulla dimostrazione di HitLeuLer, mi ci metto a studiare, sicuramente mi mancano un bel pò di nozioni. Intanto...posso chiedere se dire che l'ordine moltiplicativo di $ 2^n $ alla base 3 è $ 2^{n-2} $ equivale a dire che l'ordine moltiplicativo di $ 2^n $ modulo 3 è $ 2^{n-2} $? (in tal caso, da cosa lo si ricava? uff...non ci ho kapito nieeente!!), grazie mille ad entrambi.
A proposito, ve lo richiedo, (anche in alternativa alla spiegazione, se troppo lunga) sapreste consigliarmi qualche testo dove potrei capirci qualcosa in più?
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Re: ..domande stupide..

Messaggio da HiTLeuLeR »

ikkio ha scritto:[...] posso chiedere se dire che l'ordine moltiplicativo e blahblahblah [...] A proposito, ve lo richiedo [...]: sapreste consigliarmi qualche testo dove potrei capirci qualcosa in più?
Search function is your friend.
ikkio
Messaggi: 5
Iscritto il: 03 mag 2006, 12:44

Messaggio da ikkio »

...tempestivo!!
Avatar utente
CeRe
Messaggi: 169
Iscritto il: 30 mar 2006, 14:41

Messaggio da CeRe »

[img]http://img74.imageshack.us/img74/9892/userbar496435bw3.gif[/img]
Omega
Messaggi: 13
Iscritto il: 05 mag 2006, 03:40

Messaggio da Omega »

Salve, anch'io mi sto cimentando da poco con i problemi delle olimpiadi, il primo caso lo avrei risolto esattamente come Ponnamperuma, ma sono arrivato al modulo 8 solo dopo qualche tentativo, c`e` un modo generico per scegliere il modulo da utilizzare?
I hear and I forget.
I see and I remember.
I do and I understand
Avatar utente
Ponnamperuma
Messaggi: 411
Iscritto il: 10 lug 2006, 11:47
Località: Torino

Messaggio da Ponnamperuma »

Beh, 8 tornava comodo perchè ovviamente 41 è congruo a 1 mod 8 (ma in questo caso non serve a molto, perchè congruenze interessanti, a + o -1, si avevano per 2,3,4,5,6,7,8!), ma soprattutto perchè le potenze di 2 mod 8 sono tutte congrue a 0, esclusi gli esponenti 1,2,3, per i quali tuttavia si verifica a mano che non ci sono soluzioni! :)
La grandezza dell'uomo si misura in base a quel che cerca e all'insistenza con cui egli resta alla ricerca. - Martin Heidegger

MIND torna!! :D
Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 »

Di solito si usano moduli che lascino pochi "residui quadratici".
Ad esempio un quadrato può essere congruo solo a 0,1,4 mod.8
Altri moduli sono modulo 9 (0,1,4,7), 3 (0,1) o 5 (0,1,4)...
il resto si lascia all'intuito.
ikkio
Messaggi: 5
Iscritto il: 03 mag 2006, 12:44

Messaggio da ikkio »

Raga, mi resta ancora una curiosità...
HitLeuLer è un'eccezione o c'è qualcun'altro in questo forum che ha capito la sua risoluzione e/o l'avrebbe risolto allo stesso modo?
Io...mi ci sto ancora scervellando, complimenti!

(mi serve per capire quanto stupido/ignorante devo ritenermi)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Ti confesserò, ikkio, che - per quanto giurerei d'averla letta e riletta più e più volte per correggere possibili refusi - la soluzione (come è scritta) è incomprensibile anche a me: edito!
ikkio
Messaggi: 5
Iscritto il: 03 mag 2006, 12:44

Messaggio da ikkio »

Grazie ancora, mi ci metto tutto natale, poi...ti faccio sapere.
Bel forum comunque, complimenti a tutti quelli che lo mantenegono utile e...serio. Magari ci rivediamo quando avrò imparerato qualcosina in più. :D
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Allora, vediamo se riesco a rendermi utile:

Supponiamo $ 41=3^m-2^n $

I casi m=0, n=0,1,2 sono banali.

Negli altri casi $ 3^m\equiv 1 \pmod 8 $ da cui $ m $ e' pari.

Inoltre $ -2^n\equiv -1 \pmod 3 $ da cui n e' pari.

Poniamo $ m=2a $ e $ n=2b $

Dovremmo avere $ 41=(3^a+2^b)(3^a-2^b) $ e dunque, essendo 41 un primo, $ 3^a-2^b=1 $ e $ 41=3^a+2^b $ e a questo punto non restano che pochi casi banali per valori piccoli di a e b.
"Sei la Barbara della situazione!" (Tap)
Rispondi