màxim comú divisor

a=mcd{a,b}·p
b=mcd{a,b}·q
a+b=mcd{a,b}·(q+p)


a=mcd{a,a+b}·k
a+b=mcd{a,a+b}·s
b=mcd{a,a+b}·(s+(-k))


mcd{a,a+b}·(s+(-k))=mcd{a,b}·q
mcd{a,a+b}·s=mcd{a,b}·q+mcd{a,a+b}·k
mcd{a,b}·(q+p)=mcd{a,b}·q+mcd{a,a+b}·k
mcd{a,b}·p=mcd{a,a+b}·k & mcd{p,k}=1
mcd{a,b}=mcd{a,a+b}·(k/p) & ( p=(mk) or  k=(np) )
mcd{a,b}=mcd{a,a+b}·(p/p) & ( (1/m)=(k/p) or  (1/n)=(p/k) ) ==> (n=1  & m=1)


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


mcd{a,a+1}=mcd{a,1}=1








mcd{8,24}=mcd{8,8+16}=mcd{8,16}=mcd{8,8+8}=mcd{8,8}=8
mcd{10,15}=mcd{10,10+5}=mcd{10,5}=mcd{5+5,5}=mcd{5,5}=5


mcd{4k+1,14k+3}=mcd{4k+1,4k+1+10k+2}=mcd{4k+1,10k+2}=...
...mcd{4k+1,6k+1}=mcd{4k+1,2k}=mcd{2k+2k+1,2k}=mcd{2k+1,2k}=1




a=mcd{a,b}·p
b=mcd{a,b}·q
na=mcd{a,b}·np
nb=mcd{a,b}·nq
na=mcd{na,nb}·p
nb=mcd{na,nb}·q
n(a+b)=mcd{na,nb}·(p+q)
n·mcd{a,b}·(p+q)=mcd{na,nb}·(p+q)
n·mcd{a,b}=mcd{na,nb}


descens inductiu:
mcd{(n+1)a,(n+1)b}=mcd{na,nb}+mcd{a,b}
mcd{(n+1)a,(n+1)b}=n·mcd{a,b}+mcd{a,b}
mcd{(n+1)a,(n+1)b}=(n+1)·mcd{a,b}


mcd{3k,6k}=mcd{(2+1)k,(2+1)2k}=mcd{2k,4k}+mcd{k,2k}=2k+k=3k






a=mcd{a,na}·p
na=mcd{a,na}·np
(n+1)a=mcd{a,na}·(n+1)p
(n+1)a=mcd{a,a+na}·(n+1)p
(n+1)a=mcd{a,(n+1)a}·(n+1)p


mcd{6k+1,12k+2}=mcd{6k+1,2·(6k+1)}=6k+1






mcd{a,a^{n}}=a


n+1=2k+1 & n^{2}+1=4k^{2}+1
mcd{2k+1,2k(2k)+1}=1 & k=(1/2)
n+1=2k+2 & n^{2}+1=4k^{2}+4k+2
mcd{2k+2,4k^{2}+4k+2}=2·mcd{k+1,2k^{2}+k+k+1}=...
...2·mcd{k+1,k(2k+1)}=2 & 2k+1=m(1+(1/k)) & k=1



mcd{a,b}=1 & d=a+(-b)
nd=an+n(-b)
(n+1)d=a(n+1)+(n+1)(-b)
mcd{an,nb}=n


6=12+(-6)
6=2·6+6·(-1)
4=16+(-12)
4=4·4+4·(-3)
10=20+(-10)
10=2·10+10·(-1)
24=36+(-12)
12·2=3·12+12·(-1)
12=18+(-6)
6·2=3·6+6·(-1)
12=72+(-60)
12=6·12+12·(-5)
54=72+(-18)
18·3=4·18+18·(-1)
105=120+(-15)
15·7=8·15+15·(-1)




1=3·5+2·(-7)


mcd{2k,3k+1}=mcd{2k,k+1}
si k=2p+1 ==> mcd{2k,k+1}=mcd{4p+2,2p+2}=2·mcd{2p+1,p+1}=2·mcd{p,p+1}=2
si k=2p ==> mcd{2k,k+1}=mcd{4p,2p+1}=1 & 2p+1=4q & p=2q+(-1)(1/2)




a^{2}=(mcd{a,b}·p)^{2}
b^{2}=(mcd{a,b}·q)^{2}
2ab=(mcd{a,b})^{2}·(2pq)
mcd{a^{2},2ab,b^{2}}=(mcd{a,b})^{2}


a^{n} = (mcd{a,b}·p)^{n}
b^{n} = (mcd{a,b}·q)^{n}
[ n // k ]a^{n+(-k)}b^{k} = (mcd{a,b})^{n}·( [ n // k ]p^{n+(-k)}q^{k} )
[ n // n+(-k) ]a^{k}b^{n+(-k)} = (mcd{a,b})^{n}·( [ n // n+(-k) ]p^{k}q^{n+(-k)} )
mcd{a^{n},...,[ n // k ]a^{n+(-k)}b^{k},...,[ n // n+(-k) ]a^{k}b^{n+(-k)},...,b^{n}}=(mcd{a,b})^{n}





ax+by=au_{n}+bv_{n}
ax+by=a(x+(-1)nb)+b(y+na)
ax+by=a(x+(-1)nb)+b(y+na)+(-1)ab+ab
ax+by=a(x+(-1)(n+1)b)+b(y+(n+1)a)
ax+by=au_{n+1}+bv_{n+1}