41 Cattivo!
41 Cattivo!
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!
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!
Re: 41 Cattivo!
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.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.
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.
- Ponnamperuma
- Messaggi: 411
- Iscritto il: 10 lug 2006, 11:47
- Località: Torino
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!
$ 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!
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
MIND torna!! :D
..domande stupide..
...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ù?
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ù?
Re: ..domande stupide..
Search function is your friend.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ù?
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
I see and I remember.
I do and I understand
- Ponnamperuma
- Messaggi: 411
- Iscritto il: 10 lug 2006, 11:47
- Località: Torino
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
MIND torna!! :D
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.
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)