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

RMP-02: Generalized approach for finding out all the possible combinations of NxN dimensional cubes + some rubik's cube graph theory

Date: 9-26-2017 Original Question: By how many different ways a rubik’s cube can be arranged? Solution: A rubik’s cube has 8 corners, which can be arranged in 8! different positions,and have 3 possible orientations,which gives 3^8 possibilities.But only ⅓  of them have the correct corner orientation as the original rubik’s cube. 12 edges give you 12! Different positions and 2 possible orientations give you 2^12 possibilities. ½  of them have the correct edge orientation of the rubik’s cube,and only ½ of the possible combinations is achievable because no two pieces can be moved by isolation,so to sum up, Follow up question,is there any generalized approach for finding out all the possible combinations of NxN dimensional cubes? Trying to solve this problem analytically I met a lot of hurdles,as the possible different combinations for the cubes of even dimensions were different than the ones of odd dimensions, because of orientational parity of even dimensioned ...
Post a Comment
Read more