Proprietà MCD

[androidiano]

consideriamo alcune proprietà del MCD, dati due numeri naturali a e b con a>b

1) MCD(a,b) = MCD(a,a-b) = MCD(b,a-b)

dim (pensata da me)

sia c il MCD tra a e b allora posso scrivere a = n*c e b = m*c, con n e m numeri naturali e n>m
quindi a-b = n*c - m*c = c(n-m) -> MCD(a,b) = MCD(a,a-b) = MCD(c*n,c(n-m)) = c

analoga dimostrazione per (b,a-b)

2) MCD(a,b) = MCD(a,r) = MCD(b,r) dove r indica il resto tra a e b r = a mod b

come si dimostra?

[Zero87]

"androidiano":2) MCD(a,b) = MCD(a,r) = MCD(b,r) dove r indica il resto tra a e b r = a mod b

come si dimostra?

La dimostrazione non la so a memoria, ma sta su qualsiasi testo che tratta di MCD ma, più in particolare, che tratta dell'algoritmo euclideo per il calcolo del MCD che si basa proprio su quella proprietà.

Per il primo, così a occhio, mi sa che è un caso che si può condurre al secondo, ma aspetta pareri più esperti.

EDIT
Sta anche su wikipedia alla voce "Algoritmo di Euclide", ma quella italiana se la cava in 4 parole mentre quella inglese è decisamente meglio [size=85](ho prestato il libro di crittografia, 'naggia...)[/size]

[Maci86]

C'è un passaggio fatto con troppa disinvoltura, per gli algebristi almeno:
$MCD(c*n,c(n-m)) = c$
Devi dimostrarlo

[androidiano]

allora se a = c*n e b = c*m n e m non hanno fattori in comune tra loro (altrimenti finirebbero in c) quindi n e n-m sono primi tra loro e l'unico fattore comune è c

[Maci86]

Ottimo!
$r=_b a => r-a=_b 0 => r-a=_b b*k$
Prova a vedere se questo ti da qualche idea!

[androidiano]

la seconda proprietà non capisco come dimostrarla non ho nemmeno il tempo perché sto studiando per l'esame di programmazione 1 e nel ripetere una lezione su alcune function C per problemi matematici ho rivisto l'algoritmo di Euclide, nelle slide si elencano queste proprietà (senza dimostrarle) la mia era una semplice curiosità (da simpatizzante della materia) se qualcuno di voi mi da una dimostrazione gli sarò molto grato