números

Teorema:

mcd{a,b} = mcd{a,a+b}

Demostració:

mcd{a,b}·k_{a} = a & mcd{a,b}·k_{b} = b

mcd{a,b}·( k_{a}+k_{b} ) = a+b

mcd{a,b} | mcd{a,a+b}

mcd{a,a+b}·k_{a} = a & mcd{a,a+b}·k_{a+b} = a+b

mcd{a,a+b}·( k_{a+b}+(-1)·k_{a} ) = b

mcd{a,a+b} | mcd{a,b}

mcd{nk,(n+1)k} = mcd{nk,k} = k·mcd{n,1} = k