Solution of Diophantine equation ax + by = c, by means of Euclidean algorithm
12 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
function [d,p,q,r,s] = euklidalg(a,b,c);
% Solution of Diophantine equation ax + by = c
% by means of Euclidean algorithm
% The greatest common divisor is the last nonzero remainder
% Back substitution:
% coefficients of the linear combination p, q
% r = -b/d, s = a/d
%
% test of equation correctness:
if isempty(find(a)) | isempty(find(b))
display('Diophantine equation is not given correctly!')
p=0; q=0; d=0; s=0; r=0;
return
end
alfa=a; beta=b; rem=a;
% search for the greatest common divisor:
i=0;
n=abs(length(a)-length(b))+1;
if n == 1
n=n+1;
end
% test of zero remainder:
while norm(rem,inf) > 100*eps
i=i+1;
% elimination the zero leading coefficients:
ind=find(beta);
beta=beta(ind(1):length(beta));
% quotient and remainder:
[quot,rem]=deconv(alfa,beta);
i0=1+n-length(quot);
% storing of quotients:
qq(i,i0:n)=quot;
% shift of polynomials:
alfa=beta; beta=rem;
end
% recurrent computation of the coefficients
d=alfa; p=0; q=1; m=i-1;
for i=m:-1:1
r=p; p=q
% formal rearrangement for polynomial sum executing:
rr=zeros(1,length(qq(i,:))+length(p)-1);
rr(length(rr)-length(r)+1:length(rr))=r;
% computation of further element of the sequence:
q=rr-conv(qq(i,:),p);
end
% normalization of polynomial:
ind=find(q); q=q(ind(1):length(q));
% general solution of the reduced equation:
r=-deconv(b,d); s=deconv(a,d);
return
I want solve this:
so my insert this:
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1601286/image.png)
a = [1, -1];
b = [0, 1, -2];
c = 1;
the result:
p = 1
d = 1
p = 1
q = -1
r = 0 -1 2
but the correct is:![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1601291/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1601291/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1601296/image.png)
Have you any idea? or some Euclidean algorithm to solve diophatine.
7 comentarios
Respuestas (1)
Hassaan
el 26 de En. de 2024
Editada: Hassaan
el 26 de En. de 2024
@Marek Hutta With a = [1, -1] and b = [0, 1, -2], it's unclear how these relate as a system of equations because of the differing lengths.
-----------------------------------------------------------------------------------------------------------------------------------------------------
If you find the solution helpful and it resolves your issue, it would be greatly appreciated if you could accept the answer. Also, leaving an upvote and a comment are also wonderful ways to provide feedback.
It's important to note that the advice and code are based on limited information and meant for educational purposes. Users should verify and adapt the code to their specific needs, ensuring compatibility and adherence to ethical standards.
Professional Interests
- Technical Services and Consulting
- Embedded Systems | Firmware Developement | Simulations
- Electrical and Electronics Engineering
Feel free to contact me.
2 comentarios
Ver también
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!