Numeri coprimi
Perchè se e solo se $(h,n)=1$ allora esistono due interi $x$, $y$ tali che $hx+ny=k$ con $k=\{ 0,1, \cdots , n-1 \}$ .
Risposte
Dove l'hai trovato questo esercizio? Sicuro che sia esattamente quella la traccia (non credo!)?
A me così com'è scritta pare falsa, sia $(2,4)=2$, eppure se $x=-1,y=1$ ottengo $-2+4=2 in {0,1,2,3}$.
Non che era se $(h,n)=1$ allora esistono due interi... ?
A me così com'è scritta pare falsa, sia $(2,4)=2$, eppure se $x=-1,y=1$ ottengo $-2+4=2 in {0,1,2,3}$.
Non che era se $(h,n)=1$ allora esistono due interi... ?
Beh la differenza è il per ogni prima di $k$.
L'implicazione $rArr$ non è difficile.
Infatti se $(h,n)=1$ per l'identità di Bezout sappiamo che esistono $alpha,beta inZZ$ tali che $alphah+betan=1$. A questo punto basta osservare che moltiplicando per $k in {0,...,n-1}$ $alphak,betak in ZZ$ da cui basta porre $x=alphak$ ed $y=betak$.
$lArr$ Io proverei così. Sia $d=(h,n)$, quindi in particolare $d|n$ e $d|h$, allora dividerà ogni loro combinazione lineare $hx+ny=k$, cioè dividerà ogni $k in {0,1,...,n-1}$. Quindi in particolare $d|1$, da cui segui $d=1$.
Credo che così possa andar bene
EDIT: una piccola precisazione, giusto per amor di completezza. Ovviamente se $d|1$ allora $d=+-1$. Ma il massimo comun divisore è unico a meno di associati, quindi ai nostri fini possiamo dire sicuramente che $d=1$
L'implicazione $rArr$ non è difficile.
Infatti se $(h,n)=1$ per l'identità di Bezout sappiamo che esistono $alpha,beta inZZ$ tali che $alphah+betan=1$. A questo punto basta osservare che moltiplicando per $k in {0,...,n-1}$ $alphak,betak in ZZ$ da cui basta porre $x=alphak$ ed $y=betak$.
$lArr$ Io proverei così. Sia $d=(h,n)$, quindi in particolare $d|n$ e $d|h$, allora dividerà ogni loro combinazione lineare $hx+ny=k$, cioè dividerà ogni $k in {0,1,...,n-1}$. Quindi in particolare $d|1$, da cui segui $d=1$.
Credo che così possa andar bene
EDIT: una piccola precisazione, giusto per amor di completezza. Ovviamente se $d|1$ allora $d=+-1$. Ma il massimo comun divisore è unico a meno di associati, quindi ai nostri fini possiamo dire sicuramente che $d=1$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo