41 Cattivo!

[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 !! ), 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

(cmq...chiedo scusa per dove l'ho messo, ma me ne sono accorto dopo che era il posto sbagliato, non sono riuscito a spostarlo ) PS. L'ho spostato, grazie a skZ!

[HiTLeuLeR]

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.

[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! ). 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!

[ikkio]

...foooorte!
Quella di Ponnamperuma l'ho capita tutta , 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ù?

[HiTLeuLeR]

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

...tempestivo!!

[CeRe]

http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=5570

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

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

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

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)

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

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

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