Skip to main content

Solving Linear Diophantine Equations for all integer solutions Using Python

   What is a linear Diophantine Equation?

The simplest linear Diophantine equation takes the form ax + by = d, where a, b and c are given integers. The solutions are described by the following theorem:
This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + kv, y − ku), where k is an arbitrary integer, and u and v are the quotients of a and b(respectively) by the greatest common divisor of a and b. (source: wiki)


To know whether a linear diophantine equation has integer solutions,  we use the principles of Bézout's identity which states that in a linear diophantine equation ax+by=d, if a and b are nonzero integers and d their greatest common divisor,there exists integer solutions for both x and y.

Linear diophantine equations can be solved using substitution or more preferably Extended Euclidean Algorithm. Solving a linear diophantine equation is fairly easy by computer too. Here's a code in python that I made recently,the steps are described in the comments with the code.

Here's a sample output










Labels:

Comments

Post a Comment

Popular posts from this blog

Using Python, Quadratic approximation of sine function without the idea of limits or infinitesimal quantities (Mini Research Paper)

The question that I actually I started out was, Is there any way to express transcendental functions using polynomials avoiding the idea of limits or infinitesimal quantities?   Origin of the Question Nowadays,we learn about the Cauchy-Weierstrass interpretation of limits in our calculus classes.Although I genuinely think that it works and it’s more convenient but I thought there would be creative other ways to do this without the idea of estimating infinitesimal quantities.I found one paper named “ The Lost Calculus ”[1],it avoids the idea of abstract limits but fails when it comes to transcendental functions.I knew that if I broke down the sine function to be humble polynomials I could than use something like Descartes’s method[1] of Tangents to that polynomial to get the derivative without using the idea of limits. That’s when I was stumbled upon this question. First thing that came to my mind was a sine function,I was thinking if there was any way to represen...
2 comments
Read more

Quantum Mechanics- A conceptual introduction

“ Anyone who thinks they can talk about Quantum Mechanics without getting dizzy hasn’t yet understood the first word of it. “ - Niels Bohr Quantum Mechanics is not something that can be predicted by using normal senses or intuition. From the dawn of civilization,we’ve been doing basic physics.Even in the stone ages,when someone threw a brick at us,we didn’t calculate the trajectory or the velocity vector of that brick to know where it’s path. We used our intuition,in a macroscopic world, we learned to predict as we became more and more evolved species.Everything follows our intuition when we do something in our day to day life,by using our classical mechanics and logical absolute way of thinking. But things are different in a microscopic level,those things are beyond our senses,and classical mechanics fails to describe it in an orderly manner. I think our leap into microscopic world started when we really tried to push classical mechanics to objects at a very small level,in...
2 comments
Read more