OliForum Matematico

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

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

sai solo che $ ord_{2^{1989}}m | \phi{2^{1989}}=2^{1988} $, non che sia proprio quello il minimo..

exodd ha scritto:n è multiplo dell'ord moltiplicativo di m mod 2 alla 1989
quindi 2 alla 1988 divide n....

Puoi postare i passaggi più dettagliati, dato che secondo me non è proprio così?
Poi, scrivere una dimostrazione ordinata e pulita non fa mai male comunque .

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!

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?

Il minimo è zero non uno! $ n=0 $

Il passo successivo pensavo che volessi sapere (a parte il caso banale di cui sopra) quale fosse il minimo e quindi procedo con il logaritmo discreto.

Mi ci vuole un poco di tempo però per scriverlo...

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.

Negli interi positivi è opinabile l'inserimento dello zero o meno, ho letto attentamente ed in ogni caso ho risposto ad entrambe... mi manca solo di esplicitare il logaritmo discreto

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?

"Intero positivo" vuol dire >0, non e' opinabile la presenza dello zero. Altrimenti non ci sarebbe la notazione "intero non negativo"

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?

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.

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!

come al solito, qui c'erano scritte solamente cavolate..

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.

Azz... non avevo visto la soluzione di exodd, adesso credo che la mia sia proprio sbagliata...