Algoritmo di euclide
salve a tutti 
,
in un esercizio in cui mi viene chiesto di calcolarmi il MCD tramite algoritmo di euclide, mi viene anche chiesto quali valori può assumere p se p= 1001 a + 33 b. ora a e b appartengono all'insieme dei numeri interi. 1001 e 33 sono i numeri interessati al calcolo del MCD.
quello che ho ipotizzato io e è che sapendo che esistono coefficienti a e b tali per cui MCD=1001 a + 33 b allora p può essere solamente un multiplo del mio MCD. è giusto? nel caso affermativo come lo posso dimostrare?
grazie mille a tutti
,in un esercizio in cui mi viene chiesto di calcolarmi il MCD tramite algoritmo di euclide, mi viene anche chiesto quali valori può assumere p se p= 1001 a + 33 b. ora a e b appartengono all'insieme dei numeri interi. 1001 e 33 sono i numeri interessati al calcolo del MCD.
quello che ho ipotizzato io e è che sapendo che esistono coefficienti a e b tali per cui MCD=1001 a + 33 b allora p può essere solamente un multiplo del mio MCD. è giusto? nel caso affermativo come lo posso dimostrare?
grazie mille a tutti
Risposte
Ciao stefy_paol 
Sì, la tua intuizione è corretta e si può dimostrare anche in maniera abbastanza semplice. Si può facilmente determinare che $MCD(1001, 33) = 11$. Ora, per l'identità di Bezout (che hai trascritto in precedenza), possiamo scegliere $a, b \in ZZ$ tali che $11 = 1001 a + 33 b$. Ora se al posto di $11$ nell'espressione precedente poniamo un generico $p$ possiamo scrivere $p = 1001 c + 33 d$ (ho cambiato i nomi delle variabili per rimanere generico). Ora però essendo $11$ l'MCD tra i nostri due valori iniziali $1001$ e $33$ possiamo scrivere $1001 = 11 \cdot 91$ e $33 = 11 \cdot 3$. Se sostituisci tali espressioni in quella del nostro $p$ arrivi facilmente alla conclusione.
Sì, la tua intuizione è corretta e si può dimostrare anche in maniera abbastanza semplice. Si può facilmente determinare che $MCD(1001, 33) = 11$. Ora, per l'identità di Bezout (che hai trascritto in precedenza), possiamo scegliere $a, b \in ZZ$ tali che $11 = 1001 a + 33 b$. Ora se al posto di $11$ nell'espressione precedente poniamo un generico $p$ possiamo scrivere $p = 1001 c + 33 d$ (ho cambiato i nomi delle variabili per rimanere generico). Ora però essendo $11$ l'MCD tra i nostri due valori iniziali $1001$ e $33$ possiamo scrivere $1001 = 11 \cdot 91$ e $33 = 11 \cdot 3$. Se sostituisci tali espressioni in quella del nostro $p$ arrivi facilmente alla conclusione.
grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo