Sia [tex]x[/tex] un numero razionale fissato. Dimostrare che esiste una sequenza [tex]x_0, x_1, x_2, . . . [/tex] di numeri razionali con le seguenti proprietà:
(a) [tex]x_0 = x[/tex];
(b) per ogni [tex]n ≥ 1[/tex] si ha o [tex]x_n = 2x_{n−1} [/tex] o [tex]x_n = 2x_{n−1} + \frac{1}{n}[/tex];
(c) [tex]x_n[/tex] è intero per qualche n.
Questa è la mia soluzione, la scrivo come esercizio di scrittura. Sarei lieto se mi facesse notare migliorie su come è scritta o eventuali errori di procedimento (se ci dovessero essere).
Testo nascosto:
Notiamo che il problema può essere riformulato così: Dimostra che è possibile generare un intero da un qualunque razionale [tex]x[/tex] con le seguenti mosse: [tex](1)[/tex] sostiture il numero con il suo doppio [tex](2)[/tex] sostiture il numero col suo doppio sommato a [tex]\frac{1}{n}[/tex], dove n è il numero della mossa
Costruiamo un algoritmo che riduce l'esponente del primo massimo al denominatore. Prima parte dell'algoritmo
Moltiplichiamo il numero per 2 finchè il denominatore della frazione ridotta ai minimi termini sia coprimo a 2 Seconda parte
Detto [tex]D[/tex] tale denominatore, notiamo che applicando la mossa [tex](1)[/tex] il denominatore rimane invariato. Chiamiamo [tex]p[/tex] il numero primo massimo nella fattorizzazione del denominatore (se non ci sono primi dispari si ha già un intero). Sia ora [tex]x_k= \frac{l}{D}[/tex], con [tex]p-1|k[/tex], ottenuto usando ancora solo mosse [tex](1)[/tex]. Notiamo ora che tutti i multipli di [tex]p-1≥k[/tex] si possono ottenere sommando più volte p-1 a k. Applichiamo ora la mossa [tex](1)[/tex] fino ad arrivare a un numero della forma [tex]x_{D*l^{-1}*(p-1)*2^{(p-1)*b}-1}[/tex] dove [tex]l^{-1}[/tex] è l'inverso moltiplicativo modulo p di l ( quindi [tex]l^{-1}<p[/tex]). b è scelto in modo che [tex]D*l^{-1}*(p-1)*2^{(p-1)*b}>k[/tex]. Ora notiamo che [tex]D*l^{-1}*(p-1)*2^{(p-1)*b}-1[/tex] si ottiene da k aggiungendo un numero congruo a -1 modulo p-1. Quindi [tex]a_{D*l^{-1}*(p-1)*2^{(p-1)*b}-1}= \frac{l*2^t}{D}[/tex], con [tex]t[/tex] congruo a -1 modulo p-1. Applichiamo ora la mossa [tex](2)[/tex] e otteniamo: [tex]a_{D*l^{-1}*(p-1)*2^{(p-1)*b}}=2* \frac{l*2^t}{D} +\frac{1}{D*l^{-1}*(p-1)*2^{(p-1)*b}}=\frac{(l*l^{-1})*2^{t+1}(p-1)*2^{(p-1)b}+1}{D*l^{-1}*(p-1)*2^{(p-1)*b}}[/tex]. Dato che t è congruo a -1 modulo p-1 usando il piccolo teorema di fermat si ha [tex](l*l^{-1})*2^{t+1}(p-1)*2^{(p-1)b}+1 \equiv -1+1 \equiv 0 (mod p)[/tex]. Quindi si può semplificare per p e l'esponente de p diminuesce di 1. Notiamo infine che il denominatore [tex]{D*l^{-1}*(p-1)*2^{(p-1)*b}}[/tex] non ha fattori maggiori o uguali a p che non abbia anche [tex]D[/tex], infatti tutti i termini del prodotto diversi da D sono minori di p tranne la potenza di due che però non ha fattori dispari. Quindi abbiamo ridotto l'esponente del primo massimo al denominatore senza generare altri primi maggiori.
Iterando più volte l'algoritmo si elimina il primo massimo e ripetendo ancora si eliminano tutti i primi dispari del denominatore. Poi si moltiplica per due fino a ottenere un intero. Si ha quindi la tesi ■
Grazie, Stef08
Ultima modifica di Stef2008 il 12/08/2023, 11:19, modificato 2 volte in totale.
Mi sembra giusta, attenzione solo che nella consegna i [tex]-1[/tex] non sono venuti a pedice, ci ho messo un attimo a capire perché fosse lecito raddoppiare...
afullo ha scritto: ↑12/08/2023, 9:28
Mi sembra giusta, attenzione solo che nella consegna i [tex]-1[/tex] non sono venuti a pedice, ci ho messo un attimo a capire perché fosse lecito raddoppiare...
Grazie mille della risposta e di avermi fatto notare l'errore nel trascrivere il testo del problema in Latex. . Ho appena sistemato
. Ho appena sistemato