Sia $ m $ un intero positivo dispari, $ m>2 $.
Trovare il più piccolo intero positivo $ n $ tale che $ 2^{1989} $ divide $ m^{n}-1 $.
IMO Shortlist 1989
2^{1989} divide m^{n} - 1
-
exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
n è multiplo dell'ord moltiplicativo di m mod 2 alla 1989
quindi 2 alla 1988 divide n
....
quindi il + piccolo n è 2 alla 1988
sono sicuro che c'è un errore, perchè mi sembra troppo semplice...
quindi 2 alla 1988 divide n
....
quindi il + piccolo n è 2 alla 1988
sono sicuro che c'è un errore, perchè mi sembra troppo semplice...
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
sai solo che $ ord_{2^{1989}}m | \phi{2^{1989}}=2^{1988} $, non che sia proprio quello il minimo.. 
Ultima modifica di jordan il 19 set 2008, 21:12, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Il minimo intero è palesemente $ 0 $!
A parte questo il successivo potrebbe essere $ 2^{1988} $ anche se non necessariamente è il minimo...
Da qui ci conviene procedere cercando di risolvere:
$ m^n \equiv 1 \mod 2^{1989} $
Da qui seguo la strada del logaritmo discreto:
Considero dapprima il caso in cui $ n < \phi(2^{1989}) = 2^{1988} $ tengo presente che la soluzione sarà comunque modulo $ \phi(2^{1989}) $...
Datemi un pochetto che vi do un risultato rigoroso!
A parte questo il successivo potrebbe essere $ 2^{1988} $ anche se non necessariamente è il minimo...
Da qui ci conviene procedere cercando di risolvere:
$ m^n \equiv 1 \mod 2^{1989} $
Da qui seguo la strada del logaritmo discreto:
Considero dapprima il caso in cui $ n < \phi(2^{1989}) = 2^{1988} $ tengo presente che la soluzione sarà comunque modulo $ \phi(2^{1989}) $...
Datemi un pochetto che vi do un risultato rigoroso!
Aspetta, sarò rincretinita io ma non ho capito cosa fai.
1. Dici che il minimo è 1 (che notazione bizzarra poi!) e non lo è, deve valere per $ m $ qualsiasi, cioè anche più piccolo di $ 2^{1989} $.
2. Non ho capito che cosa fai dopo col logaritmo discreto. Più che altro, dato che hai detto che 1 è il minimo, perchè tenti di dimostrarlo poi?
1. Dici che il minimo è 1 (che notazione bizzarra poi!) e non lo è, deve valere per $ m $ qualsiasi, cioè anche più piccolo di $ 2^{1989} $.
2. Non ho capito che cosa fai dopo col logaritmo discreto. Più che altro, dato che hai detto che 1 è il minimo, perchè tenti di dimostrarlo poi?
Leggere i testi con attenzione è sempre molto importante.
E' difficile che il minimo intero positivo che soddisfa qualcosa sia 0, in quanto 0 non è un intero positivo.
Il caso banale era già escluso dall'autore nel testo.
Detto ciò, attenzione ai punti esclamativi: dopo i numeri tendono ad essere interpretati come fattoriali.
E' difficile che il minimo intero positivo che soddisfa qualcosa sia 0, in quanto 0 non è un intero positivo.
Il caso banale era già escluso dall'autore nel testo.
Detto ciò, attenzione ai punti esclamativi: dopo i numeri tendono ad essere interpretati come fattoriali.
Ok, ora non so cosa vuol dire esplicitare il logaritmo discreto e penso che valga anche per altri, quindi o la fai per bene o, non te la prendere ma quello che hai scritto finora non ha molto senso come dimostrazione.
In ogni caso, ho una soluzione in cui questo log. non viene neanche citato ed è tra l'altro molto semplice se si conoscono le basi di teoria dei numeri.
Stradh, sei universitario?
In ogni caso, ho una soluzione in cui questo log. non viene neanche citato ed è tra l'altro molto semplice se si conoscono le basi di teoria dei numeri.
Stradh, sei universitario?
"Intero positivo" vuol dire >0, non e' opinabile la presenza dello zero. Altrimenti non ci sarebbe la notazione "intero non negativo"
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Di modi per risolverlo ce ne sono differenti, il logaritmo discreto è uno a cui non avevo mai dato il peso corretto e che mi ha risolto qualche problema ultimamente.EUCLA ha scritto:Ok, ora non so cosa vuol dire esplicitare il logaritmo discreto e penso che valga anche per altri, quindi o la fai per bene o, non te la prendere ma quello che hai scritto finora non ha molto senso come dimostrazione.
In ogni caso, ho una soluzione in cui questo log. non viene neanche citato ed è tra l'altro molto semplice se si conoscono le basi di teoria dei numeri.
Stradh, sei universitario?
Sfortunatamente a causa del mio lavoro sono poco presente e (anche come regolamento del forum) dovrei solamente fare da supporto a coloro che devono tentare questi "quesiti olimpici". Mi spiace essere lacunoso, ma mi ci vuole tempo.
Non sono solo universitario, ma lavoro già come matematico!
-
exodd
- Messaggi: 728
- Iscritto il: 09 mar 2007, 19:46
- Località: sulle pendici della provincia più alta d'europa
come al solito, qui c'erano scritte solamente cavolate..
Ultima modifica di exodd il 29 set 2008, 15:59, modificato 1 volta in totale.
Tutto è possibile: L'impossibile richiede solo più tempo
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
ispiratore del BTAEvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
in geometry, angles are angels
"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
Riscriviamo il testo
$ $m^n \equiv 1 \pmod{2^{1989}}$ $
Siamo già tutti d'accordo che
$ $n=ord_{2^{1989}}(m_i) | \phi (2^{1989})=2^{1988}$ $
e quindi $ $n$ $ deve essere della forma $ $2^k$ $
Riscriviamo ancora
$ $m^{2^{k}}-1=(m^{2^{k-1}}+1)(m^{2^{k-2}}+1)$ $$ $\cdots (m^4+1)(m^2+1)(m+1)(m-1) \equiv 0 \pmod{2^{1989}}$ $
E da qui comincio ad avere i miei dubbi...
Siccome $ $m$ $ è dispari allora deve essere congruo a 1 o -1 modulo 4 e quindi ogni termine di $ $(m^{2^{k-1}}+1)(m^{2^{k-2}}+1)$ $$ $\cdots (m^4+1)(m^2+1)$ $ è congruo a 2 modulo 4 cioè porta solo un 2 al prodotto (in tutto quindi k-1 due). Nei restanti due termini $ $(m+1)(m-1)$ $ uno deve essere congruo a 2 modulo 4 e l'altro a 0 e quindi vengono aggiunti ancora 3 due al k-1, in tutto quindi k+2 due. Quindi basta che k sia 1987.
A voi la correzione.
$ $m^n \equiv 1 \pmod{2^{1989}}$ $
Siamo già tutti d'accordo che
$ $n=ord_{2^{1989}}(m_i) | \phi (2^{1989})=2^{1988}$ $
e quindi $ $n$ $ deve essere della forma $ $2^k$ $
Riscriviamo ancora
$ $m^{2^{k}}-1=(m^{2^{k-1}}+1)(m^{2^{k-2}}+1)$ $$ $\cdots (m^4+1)(m^2+1)(m+1)(m-1) \equiv 0 \pmod{2^{1989}}$ $
E da qui comincio ad avere i miei dubbi...
Siccome $ $m$ $ è dispari allora deve essere congruo a 1 o -1 modulo 4 e quindi ogni termine di $ $(m^{2^{k-1}}+1)(m^{2^{k-2}}+1)$ $$ $\cdots (m^4+1)(m^2+1)$ $ è congruo a 2 modulo 4 cioè porta solo un 2 al prodotto (in tutto quindi k-1 due). Nei restanti due termini $ $(m+1)(m-1)$ $ uno deve essere congruo a 2 modulo 4 e l'altro a 0 e quindi vengono aggiunti ancora 3 due al k-1, in tutto quindi k+2 due. Quindi basta che k sia 1987.
A voi la correzione.
Appassionatamente BTA 197!