IMO 1971/3

[mod_2]

Dimostrare che esiste un insieme infinito di interi della forma $ $2^n-3$ $, con $ $n$ $ intero positivo, a due a due relativamente primi.

[jordan]

Una possibile (e conosciuta) soluzione: $ a_n=2^{k_n}-3, k_1=2, k_{n+1}=\varphi{(\displaystyle \prod_{i=1}^n{a_i})}+2 $

[Inkio]

Molto probabilmente ho capito male la consegna, perchè altrimenti non sarebbe da IMO....ma se ho capito bene, si potrebbe dire che se n=3, allora 8-3=5, e dal momento che esistono infiniti numeri della forma $ 2^n-3 $non multipli di 5 vinco....Ma ripeto, penso di aver capito male...

[fph]

Uhm, il problema è che con "a due a due relativamente primi" si intende "scelti due qualunque di essi, questi due non hanno un fattore in comune". Tu hai dimostrato che se scelgo 5 e un altro numero, non hanno un fattore comune. Però questo non basta: se per esempio i nostri numeri fossero 5, 21 e 28, allora 21 e 28 hanno un fattore in comune.

(in ogni caso, non ti fare spaventare dalla parola "IMO": i problemi delle olimpiadi internazionali degli anni 60-70 spesso risultano molto più abbordabili rispetto a quelli di oggi).

[mod_2]

@jordan
vai alla caccia dei messaggi vecchi eh?

Sembra proprio che il problema sia fatto per la tua soluzione. Ne hai anche un'altra vero?

[jordan]

@jordan
vai alla caccia dei messaggi vecchi eh?

Ciao mod_2!Eh, si, anche notando che ho molti problemi non risolti..

Comunque per la soluzione mia ho provato ieri, considerando che $ 2^{2^a}-1|2^{2^{a+b}}-1 $, ma il fatto è che i primi di $ 2^n-3 $ non puoi conoscerli a priopri..

[dario2994]

Tanto per dire di aver risolto un IMO posto xD
Non sono sicuro della soluzione perchè non ho capito a pieno le proprietà dell'ordine moltiplicativo... ma ci provo.
Il primo elemento dell'insieme dico che è:
$ 2^3-3=5 $
Per generare il nuovo numero appartenente all'insieme faccio così:
Chiamo k il prodotto di tutti i termini precedenti nell'insieme.
Poichè 2 e k sono ovviamente coprimi (nessun elemento è pari) esiste l'ordine moltiplicativo di 2 modulo k e per definizione so che:
$ 2^{O_k(2)}\equiv 1 \pmod{k} $
A questo punto se moltiplico per 4 ottengo:
$ 2^{O_k(2)+2}\equiv 4 \pmod{k}\Rightarrow 2^{O_k(2)+2}-3\equiv 1 \pmod{k} $
Perciò per le proprietà delle congruenze ho creato un termine successivo coprimo con tutti gli altri e quindi l'insieme è infinito.

[julio14]

Guarda che è sostanzialmente la stessa soluzione di jordan... solo che lui ha usato la phi e tu l'ordine, ma non cambia molto, anche perché la phi è un multiplo dell'ordine.

[dario2994]

Uhm... si leggendola è praticamente la stessa xD