function [prim,t2]=euclid(t,m)
%algoritmul euclid extins imi calculeaza t^(-1) atunci
%cand cunosc t si m, iar t si m sunt prime intre ele
t=abs(t);
m=abs(m);
%initializare pentru cmmdc t0=0 si t1=1 => cmmdc este t
r0=m;
t0=0;
t1=1;
prim=1;
while(t>1)
    q=floor(m/t);
    r=m-q*t;
        if(r == 0) %verific daca m/t este un nr intreg
            prim = 0;
            return; %nu are inversa
        end
    m=t;
    t=r;
    t2=mod(t0-q*t1,r0);  %calculez t^(-1)
    t0 = t1;
    t1 = t2;
end

function [prim,t2]=euclid(t,m)
%algoritmul euclid extins imi calculeaza t^(-1) atunci
%cand cunosc t si m, iar t si m sunt prime intre ele
t=abs(t);
m=abs(m);
if(t<m)
    aux=t;
    t=m;
    m=aux;
end
%initializare pentru cmmdc t0=0 si t1=1 => cmmdc este t
r0 = t;
t0 = 0;
t1 = 1;
prim = 1;
while(m>1)
    q=floor(t/m);
    r=t-q*m;
    if(r == 0) %verific daca t/m este un nr intreg
        prim = 0;
        return; %nu are inversa
    end
    t=m; %t devine m
    m=r; %m devine diferenta dintre t si raporul t/m
    t2 = mod(t0-q*t1,r0); %calculez t^(-1)
    t0 = t1;
    t1 = t2;
end