Pagina 1 di 1

MDC ,mcm

Inviato: 27 lug 2012, 15:46
da Robertopphneimer
Qualcuno saprebbe dimostrarmi che $ MCD(a,b)=MCD(b,b mod a) $

Re: MDC ,mcm

Inviato: 27 lug 2012, 16:14
da jordan
La notazione b mod a non ha molto significato, dato che non descrive un intero, ma una intera classe di esso.

In ogni caso la tua richiesta e' equivalente a MCD(a,b)=MCD(a,b+ka) per qualunque intero k..

Re: MDC ,mcm

Inviato: 27 lug 2012, 16:29
da Robertopphneimer
no m,i spiace non capisco...come può essere MCD(a,b+ka) equivalente??c'è una qualche dimostrazione??
io per il b mod a ho pensato che se un numero divide entrambi allora (ed è il massimo) allora dovrebbe essere lo stesso massimo a dividere sia b che il resto di a perché $ a=bq+r $ perciò $ r=a-bq $e se contiamo MCD come q r|q e quindi la cosa è equivalente.(spero sia giusta :S)

Re: MDC ,mcm

Inviato: 27 lug 2012, 16:45
da jordan
Allora, fissi due interi positivi $x,y$.

Ora, se un qualunque intero $d$ divide sia $x$ che $y$ , allora $d$ divide anche tutte le combinazioni lineari dei due, fin qui ci siamo?

In altre parole $d\mid \text{gcd}(x,y) \implies d\mid \alpha x + \beta y$ per ogni $\alpha, \beta $ interi.

Scegliamo $d$ il piu grande possibile, cioè $d=\text{gcd}(x,y)$: hai che $\text{gcd}(x,y) \mid \alpha x + \beta y$ per ogni $\alpha, \beta $ interi.

In piu', dato che $\text{gcd}(x,y) \mid x$ allora $\text{gcd}(x,y) \mid \text{gcd}(x, \alpha x + \beta y)$ per ogni $\alpha, \beta $ interi.

Re: MDC ,mcm

Inviato: 28 lug 2012, 12:00
da Robertopphneimer
Ok buona come dimostrazione :D ma la tua è anche più generale suppongo poiché c'è anche il beta mentre prima lo assumevi =1 ..ma tanto comunque se è intero valgono tutte le combinazioni lineari...perciò anche la divisione con resto..(spero di non sbagliare)

Re: MDC ,mcm

Inviato: 28 lug 2012, 13:47
da Robertopphneimer
Colgo l'occasione per chiarificare un'incertezza :
Sulle dispense delle olimpiadi matematiche hanno scritto due configurazioni per la funzione $ mod $.
Una volta hanno scritto $ a mod b=r $, un'altra volta $ a=b(mod m) $ scusate potete dirmi le possibili configurazioni per questa funzione(nuova per me)?? anche le modalità di scrivere formule inverse o cose del genere .