Massimo comun divisore
Qualche anima pia che possiede il Niven-Zuckerman-Montgomery su Teoria dei Numeri può aiutarmi a risolvere l'esercizio 40 a pagina 19? Mi ci sono arenato (se poi esistesse un manualetto con tutte le soluzioni, ancora meglio).
Risposte
Non vedo ancora una soluzione - e non è detto che la vedrò 
- però posso aiutare chi non ha il libro in questione e saprebbe come darti una mano. 
Per chi non avesse il suddetto testo (traduco alla buona dato che è in inglese)
"Con le $x_i$ e le $y_i$ determinate nel problema 39, si mostri che $x_(i-1)y_i-x_i y_(i-1) = (-1)^i$ per $i=0,1,2, ... ,j+1$. Dedurre che $(x_i , y_i)=1$ per $i=-1,0,1,...,j+1$."
Cito anche il problema 39 per ovvi motivi
"Supponiamo che il metodo utilizzato nella dimostrazione del teorema 1.11 si occupi della ricerca ricerca di $x$ e $y$ affinché $bx+cy=g$. Quindi $bx_i + cy_i=r_i$. Mostrare che $(-1)^i x_i \le 0$ e $(-1)^i y_i \ge 0$ per $i= -1,0,1,...,j+1$. Dedurre che $|x_(i+1)|=|x_(i-1)|+q_(i+1) |x_i|$ e che $|y_(i+1)|=|y_(i-1)|+q_(i-1) |y_i|$ per $i=0,1,...,j$."
Il teorema a cui si fa riferimento (1.11) è quello dell'algoritmo euclideo per il calcolo del MCD.
- però posso aiutare chi non ha il libro in questione e saprebbe come darti una mano. "ZetaFunction":
Qualche anima pia che possiede il Niven-Zuckerman-Montgomery su Teoria dei Numeri può aiutarmi a risolvere l'esercizio 40 a pagina 19?
Per chi non avesse il suddetto testo (traduco alla buona dato che è in inglese)
"Con le $x_i$ e le $y_i$ determinate nel problema 39, si mostri che $x_(i-1)y_i-x_i y_(i-1) = (-1)^i$ per $i=0,1,2, ... ,j+1$. Dedurre che $(x_i , y_i)=1$ per $i=-1,0,1,...,j+1$."
Cito anche il problema 39 per ovvi motivi
"Supponiamo che il metodo utilizzato nella dimostrazione del teorema 1.11 si occupi della ricerca ricerca di $x$ e $y$ affinché $bx+cy=g$. Quindi $bx_i + cy_i=r_i$. Mostrare che $(-1)^i x_i \le 0$ e $(-1)^i y_i \ge 0$ per $i= -1,0,1,...,j+1$. Dedurre che $|x_(i+1)|=|x_(i-1)|+q_(i+1) |x_i|$ e che $|y_(i+1)|=|y_(i-1)|+q_(i-1) |y_i|$ per $i=0,1,...,j$."
Il teorema a cui si fa riferimento (1.11) è quello dell'algoritmo euclideo per il calcolo del MCD.
Vabbé, ma anche detto così non è che uno capisca tutto... dammi na manina!!!
"ZetaFunction":
Vabbé, ma anche detto così non è che uno capisca tutto... dammi na manina!!!
Se sapevo come si faceva, ti avrei dato certamente una mano (oltre che a scrivere il testo): le mie conoscenze di tdn sono appassionative e non tecniche.
Poi non vuol dire comunque che non ci sto pensando a come venirne a capo!
Magari posso dirti di iniziare a buttare giù qualche idea del tuo ragionamento: 2 teste sono meglio di una. (Magari finisce che passa un altro utente e in 4 e 4 otto ha una soluzione, ma se non è così... proviamoci in 2
)
Perfetto, dopo allora spremo le meningi 
Mi accorgo adesso 
che ho chiesto il problema sbagliato, quello da risolvere è il 41 . Ovvero, dati gli es. sopra riportati, si ha che
$|x_(j+1)|=c/g$ e $|y_(j+1)|=b/g$
L'unica considerazione che sono riuscito a partorire è che tali sostituzioni effettivamente soddisfano $x_(i-1)y_i-x_i y_(i-1) = (-1)^i$, con $i=j+1$. Non mi viene in mente come dimostrarne l'unicità, un modo potrebbe esser lo sfruttare $|x_(i+1)|=|x_(i-1)|+q_(i+1) |x_i|$ e $|y_(i+1)|=|y_(i-1)|+q_(i+1) |y_i|$, ma non saprei come...
che ho chiesto il problema sbagliato, quello da risolvere è il 41 . Ovvero, dati gli es. sopra riportati, si ha che$|x_(j+1)|=c/g$ e $|y_(j+1)|=b/g$
L'unica considerazione che sono riuscito a partorire è che tali sostituzioni effettivamente soddisfano $x_(i-1)y_i-x_i y_(i-1) = (-1)^i$, con $i=j+1$. Non mi viene in mente come dimostrarne l'unicità, un modo potrebbe esser lo sfruttare $|x_(i+1)|=|x_(i-1)|+q_(i+1) |x_i|$ e $|y_(i+1)|=|y_(i-1)|+q_(i+1) |y_i|$, ma non saprei come...
Ragazzi ancora niente? Zero, qualche idea?
"ZetaFunction":
Zero, qualche idea?
Muro bianco, ZetaFunction! (Strano, però che non ha risposto nessun'altro!)
Magari è una stupidata, ma non so proprio come iniziare.
M'è venuto in mente solo di provare a ricavare $|x_(j+1)|$ e $|y_(j+1)|$ dalle relazioni del'esercizio precedente mettendo anche quella dopo nel sistemone, ma mi incarto con i calcoli e c'è troppa roba che rimane inespressa...
C'è da ristudiarsi bene il capitolo. Nei suggerimenti in fondo al libro invita ad usare il teorema 1.10, ma onestamente non capisco come.
Teorema che afferma semplicemente che se $c|ab$ e $(b,c)=1$, allora $c|a$
"ZetaFunction":
Teorema che afferma semplicemente che se $c|ab$ e $(b,c)=1$, allora $c|a$
Un teorema che mi piace e che ha smontato spesso e volentieri molte dimostrazioni/congetture di Stellinelm (che saluto nonostante tutto se osserva questo thread da anonima).
Comunque, forse ho l'illuminazione... ma dico "forse".
"ZetaFunction":
sostituzioni effettivamente soddisfano $ x_(i-1)y_i-x_i y_(i-1) = (-1)^i $, con $ i=j+1 $
Posso leggerla come identità di Bezout, da cui traggo che $x_(j+1)$ e $y_(j+1)$ hanno $1$ come massimo comun divisore: se avessi $-1$ invece che $1$ all'altro membro, cambio segno a tutto e sto apposto (tanto nell'identità di Bezout si parla di coefficienti interi, no?).
A questo punto applico il teoremuccio che hai citato e so che quindi $x_(j+1)$ e $y_(j+1)$ sono tali che $(x_(j+1), y_(j+1))=1$. Ora non ricordo chi è $b$ e $c$, ma dovremmo essere un pezzo avanti, no (almeno spero!)? (suppongo che $g$ sia il massimo comun divisore).
Sei sicuro di poterla leggere come identità di Bezout? Comunque il mcd tra i due è 1, si dimostra in un esercizio prima 
.
.
"ZetaFunction":
Sei sicuro di poterla leggere come identità di Bezout?
Guarda, ho pensato che in questa
$ x_(j)y_(j+1)-x_(j+1) y_(j) = (-1)^(j+1) $
Quelli con pedice $j$ erano i coefficienti da dare a quelli con il pedice $j+1$ in accordo alla suddetta identità. Se all'altro membro viene $-1$ cambio segno al primo membro e mi ritrovo comunque...
"ZetaFunction":
Comunque il mcd tra i due è 1, si dimostra in un esercizio prima
Chi ci ha fatto caso!
[size=80]Comunque puoi facilmente notare che a parte quei 2-3 concetti che ho studiato/inserito nella tesi di teoria dei numeri non so praticamente nulla (un pizzico di più lo so in teoria analitica dei numeri)...
[/size]
Il libro inoltre suggerisce di esaminare separatamente i casi in cui $b=0$ e $c=0$.
Cosa che tra l'altro a me pare un po' una presa per i fondelli, dato che si tratta di casi banali.
Ho avuto l'illuminazione e penso di aver risolto ^^ prossimamente la riporto.
Come non detto...
Qualche buonanima che ha una soluzione a questo (nel frattempo tralasciato) esercizio?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo