MATLAB: Linear Congruence from Euclids HCF

congruencefunctionMATLAB

I've succestfully made a function for Euclids HCF and its working. I'm trying to now make a function to use it to find Linear Congruence but I don't really know where to start, work through or end. Can anyone possibly help out?
function z = euclidshcf(x,z)
while mod(x,z) ~= 0
u = mod(x,z);
x = z ;
z = u ;
end
disp("The HCF is")
disp(z)
end

Best Answer

What is your question? I assume HCF ~ Highest Common Factor?
Google tells me HCF also might be reference to an Australian health care fund, or perhaps the Hawaii Community Foundation. There are other possibilities I'm sure. So I'm just guessing. ;-)
In MATLAB, this is implemented as GCD.
help gcd
 gcd    Greatest common divisor.
    G = gcd(A,B) is the greatest common divisor of corresponding elements
    of A and B.
The code you actually show looks like a simple implementation of the Euclidean algorithm for GCD. It should even work. The mods and swaps do what you need.
>> x = factorial(7);
>> z = 1584;
>> while mod(x,z) ~= 0
        u = mod(x,z);
        x = z ;
        z = u ;
          
    end
    disp("The HCF is")
    disp(z)
The HCF is
   144
Is it correct? 
gcd(factorial(7),1584)
ans =
   144
I did that as not a proof of correctness of course, but merely a guide to intuition, to suggest that you have written a valid implementtion of the Euclidean algorithm for the GCD. I'm too lazy today to actually want to prove anything this early in the morning.
https://en.wikipedia.org/wiki/Greatest_common_divisor
But then you say you want to use it to find linear congruence? What do you mean by that? This is probably a language issue, but I am not at all sure what you mean by that. If I had to guess, and this is purely a wild guess, you want a way to solve a simple linear Diophantine equation? For example, what integers x and y, solve the problem
23*x + 145*y = 6
for integers x and y. Is this, perhaps, what you wish to solve? That general class of problem?
In fact, GCD gives you the answer directly, if you look at the other return arguments from gcd. From the help for GCD, we see this line:
[G,C,D] = gcd(A,B) also returns C and D so that G = A.*C + B.*D.
So we can use gcd to solve the problem I showed above. That is, gcd has given us 
[G,C,D] = gcd(23,145)
G =
     1
C =
   -63
D =
    10
We can see this is valid.
23*C + 145*D
ans =
     1
Therefore, if we multiply by 6 (the number on the right hand side of our required equality)
6*(23*C + 145*D)
ans =
     6
which gives a solution in the form of integers x and y.
x = 6*C
y = 6*D
x =
  -378
y =
    60
I should add there are infinitely many solutions to the linear Diophantine problem. The one I generated is only one of infinitely many.
Again, I'm just making a wild guess as to your real question. There is a problem some of the time, when A and B are not relatively prime in that equation. That is, can we solve the problem
2*x + 12*y = 7
for integer x and y? Here the answer is no. Unless the right hand side there is also divisible by the GCD of 2 and 12, there can be no solution in integers x and y. Since GCD(2,12)=2, and 7 is NOT evenly divisible by 2, it must fail.
Do you really need to write your own code for this? WHY? Don't write code to do what is already provided if you can avoid it.
Sigh. IF you truly intend to recreate what is already provided, then you need to do some reading, perhaps here, about Bézout's identity.
https://en.wikipedia.org/wiki/Bézout%27s_identity
With a little digging, you will find a simple algorithm to solve the problem using the Euclidean algorithm. I'd still suggest you just use existing code though.
Related Question