Counting nonegative integer solutions of two variables Linear Diophantine Equation

Revision en5, by SPyofgame, 2020-11-24 17:16:55

### The equation

A Linear Diophantine Equation is an equation of the general form:

$\underset{i = 1}{\overset{n}{\Sigma}} (a_i \cdot x_i) = N$

Where $a_i$ and $N$ are given integers and $x_i$ are unknown integers.

### The problem

Given Linear Diophantine Equation of only 2 variables:

$ax + by = c$

With given integers $a, b, c$ and unknown integers $x, y$

Some interesting property

We have to count the number of $(x, y)$ non-negative integers solutions for the equation (assume that these value are under $10^9$ so that we dont deal with overflow cases\$

Can I have a simplier implementation then this ? (My algorithm based on cp-algorithm)

Recursive extended greatest common divisor
Recursive extended greatest common divisor
Find one solution ax + by = c
Shift solution
Count number solutions of ax + by = c with given range x & range y
Count all nonegative solutions (x, y) satisfy ax + by = c

#### History

Revisions

Rev. Lang. By When Δ Comment
en5 SPyofgame 2020-11-24 17:16:55 55
en4 SPyofgame 2020-11-24 17:06:42 361
en3 SPyofgame 2020-11-24 17:02:25 558 Tiny change: 'rset{n}{\Sigma}} a_i \cd' -> 'rset{n}{\SIGMA}} a_i \cd'
en2 SPyofgame 2020-11-24 16:52:29 393
en1 SPyofgame 2020-11-24 16:48:03 4234 Initial revision (published)