Euclid algorithm and its applications

we have used this algorithm in our elementary classes for finding out
the remainder no big deal !!! ; but let take this equation
1353x + 23y = 1 can you find out values of x and y without hit and trial method
yes we can how i am googling and find out numerical recipes and yeahh it
uses the gcd algorithm to find out the values of  x and   y it is called Extended_Euclidean_algorithm  today we will discuss its types and its three methods to solve this equation.As discussed in the wikipedia if we follow
Bézout's identity which says if the equation is written in the ax + by = 1
where a and b are the Bézout's coefficiants then we can write this equation
by maintaining  a and  b as it is and changing values of  x and  y
which is equal to  1;question arises why 1 here comes the existence of gcd
can we write this equation as

so i can write as

now we have to calculate the values of  x and  y without changing the values
of  a  and  b; but there is the condition i.e. you can only calculate correct
values of  x  and  y whose gcd is 1 as seen in the equation question arises
how do we calculate the values of  x and y  without changing the values
of  a  and  b this can be done with the help of three methods
1)substitution
2)recursion
3)table method
as given in the wikipedia the codes of three are availaible here and
also you can test any values

1)substitution Iterative_method(substitution)
(please test values only for those gcd of them is 1)

you can test by giving input parameters a and b at extended euclid algorithm by substitution

2) recursion recursive
(please test values only for those gcd of them is 1)

you can test by giving input parameters a and b at extended euclid algorithm by recursion
3) table method table
(please test values only for those gcd of them is 1) you can test by giving input parameters a and b at extended euclid algorithm by table

another application of the euclid algorithm is to find the
modular inversethe best explanation i would give is

we have given a and m and we have to find the value of x such that
their multiplication (a*x) bring 1 mod m
solving:if somehow we can write this in the form
extended euclid equation then we can solve it yes we can equation

where q is the qutionent of a and m as we can write

as we cannot write a and m as negative therefore x and q be negative

in the form of  ax + by  as in extended euclid algorithm
solve it for q and x and then modulus by m therefore
we are left with

here is the code

you can test by giving input parameters a and m at multiplicative inverse

i come with something more interesting in number theory till then enjoy