NEW APPROACH ALGORITHMIC SOLUTION OF
THE LINEAR DIOPHANTINE EQUATION (LDE) Ax
+ By = C

Samuel J. Flores

► To cite this version:

Samuel J. Flores. NEW APPROACH ALGORITHMIC SOLUTION OF THE LINEAR DIOPHANTINE EQUATION (LDE) Ax + By = C. 2024. hal-04500401v2

HAL Id: hal-04500401

https://hal.science/hal-04500401v2

Preprint submitted on 7 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# NEW APPROACH ALGORITHMIC SOLUTION OF THE LINEAR DIOPHANTINE EQUATION

$$ (\text{LDE}) \quad Ax + By = C $$

SAMUEL FLORES

April 6, 2024

## Abstract

Motivated by the study of certain Linear Diophantine Equations (LDE), we computed for $Ax+By = C$ solutions using an algorithmic approach based on a change of variable that allows reducing the size of the coefficients of the Linear Diophantine Equation $Ax+By = C$ where $A, B$ and $C$ are integers and they are factored as a product of two primes, one of them being even.

## 1 Introduction

Finding the solution to the Linear Diophantine Equation (LDE), $Ax + By = C$ where $A, B$ and $C$ are integers, is known in the literature, see [1,2,3]. When the integers $B$ and $C$ can be rewritten as a product of primes, we can reduce the size of the coefficients by changing the specific variable.

## 2 Main results

Let us consider the Linear Diophantine Equation defined by:

$$ Ax + By = C \qquad (1) $$

Let us assume without losing generality that the integer coefficient $A$ of equation (1) is greater than the integer coefficient $B$ of the same equation and that there are integers $\hat{A}, \hat{B}$ and $\hat{C}$ such that $A = 2 \cdot (\hat{B})^3 - 2 \cdot \hat{A}, B = (\hat{B})^3, C = \hat{C} + \hat{A} \cdot q^2$. and furthermore, equation (1) is rewritten as

$$ (2 \cdot (\hat{B})^3 - 2 \cdot \hat{A})x + \hat{B}y = \hat{C} + \hat{A} \cdot q^2. \qquad (2) $$

Here we consider case that $\hat{A}, \hat{B}$ and $\hat{C}$ can be factored as products of two primes, say $p_1$ and $p_2$ plus a constant, then
$$ \hat{A} = (p_1 \cdot p_2), \qquad (3) $$

$$ \hat{B} = (p_1 \cdot p_2 + 1), \qquad (4) $$

$$ \hat{C} = (p_1 \cdot p_2 + 1). \qquad (5) $$

Substituting equations (3), (4) and (5) into (2) we obtain

$$ (2 \cdot (p_1 \cdot p_2)^3 - 2 \cdot (p_1 \cdot p_2 + 1))x + (p_1 \cdot p_2)^3 y = (p_1 \cdot p_2) \cdot q^2. \qquad (6) $$

**Proposition 2.1.** If $p$ is a prime number and $p > 2$, then $p$ is odd.

*Proof.* Suppose that $p$ is an even prime number such that $p > 2$, then $p$ has a number of divisors greater than three, that is, 1, 2 and $p$ and combinations of them. Since $p$ is prime, the only divisors are 1 and $p$, that is, $p$ is an odd prime number. $\square$

**Theorem 2.1.** If $p$ is a product of two primes numbers, say $p_1$ and $p_2$ such that $p_1$ is even, then the Diophantine equation (6) is of the form:

$$ (2(p-1)^3 - 2p) \cdot x + (p-1)^3 \cdot y = 1 + p \cdot (1+q^2). \qquad (7) $$

where

$$ q^2 = p_1 + p_2 - 1. \qquad (8) $$

We can also reduce the size of the coefficients by changing the following variable:

$$ (p-1)^3 \cdot Y - p \cdot X = p+1. \qquad (9) $$

where

$$ X = q^2 + 2 \cdot x. \qquad (10) $$

$$ Y = y + 2 \cdot x. \qquad (11) $$

*Proof.*

$$ 0 = (p-1)^3 \cdot Y - p \cdot X - (p+1) \qquad (12) $$

$$ = (p-1)^3 \cdot (y + 2 \cdot x) - p \cdot (q^2 + 2 \cdot x) - (p+1) $$

$$ = (p-1)^3 \cdot y + 2(p-1)^3 \cdot x - p \cdot q^2 + 2p \cdot x - (p+1) $$

$$ = (2(p-1)^3 - 2p) \cdot x + (p-1)^3 \cdot y = 1 + p \cdot (1+q^2). \qquad \square $$
## 2.1 Algorithm to calculate the Diophantine Linear Equation (SDLE), $(p-1)^3 \cdot Y - p \cdot X = p+1$ where $p = p_1 \cdot p_2$ are primes numbers and $q^2 = p_1 + p_2 + 1$.

**Step 1:** Using the previous theorem (2.1) we have that:

$$X = q^2 + 2 \cdot x. \tag{13}$$

$$Y = y + 2 \cdot x.$$

**Step 2:** In **Step 1**, we solve $X$ of $(p-1)^3 \cdot Y - p \cdot X = p+1$:

$$X = \frac{(p-1)^3 \cdot Y - (p+1)}{p}. \tag{14}$$

**Step 3:** Exists an fixed integer $Y = -1$ such that $X$ in the **Step 2** is an integer.

**Step 4:** We solve $x, y$ the **Step 1** using $X, Y$ from **Step 2**, obtain two particular solutions, let's say $x_0$ and $y_0$ of the Linear Diophantine Equation (EDL).

$$(2(p-1)^3 - 2p) \cdot x + (p-1)^3 \cdot y = 1 + p \cdot (1 + q^2). \tag{15}$$

that is

$$(2(p-1)^3 - 2p) \cdot x_0 + (p-1)^3 \cdot y_0 = 1 + p \cdot (1 + q^2). \tag{16}$$

**Step 5:** The general solution of the Linear Diophantine Equation (EDL).

$$(2(p-1)^3 - 2p) \cdot x + (p-1)^3 \cdot y = 1 + p \cdot (1 + q^2). \tag{17}$$

is

$$x = x_0 + p^3 \cdot t. \tag{18}$$

$$y = y_0 - (2(p-1)^3 - 2p).$$

where $t \in \mathbb{Z}$.

**Example 2.2.** Solve:

$$\bullet 238x + 125y = 31.$$

**Step 1:** Using the previous theorem (2.1) we have that:

$$X = 4 + 2 \cdot x. \tag{19}$$

$$Y = y + 2 \cdot x.$$

Rewriting the equation $238x + 125y = 31$, we obtain

$$5^3 \cdot (y + 2 \cdot x) - 6 \cdot (4 + 2x) = 7. \tag{20}$$
where $p = p_1 \cdot p_2$ an $p_1 = 2, p_2 = 3$, that is

$$5^3 \cdot (y + 2 \cdot x) - 12 \cdot (2 + x) = 7. \qquad (21)$$

$$125 \cdot Y - 12 \cdot X = 7. \qquad (22)$$

**Step 2:** In **Step 1**, we solve $X$ of $5^3 \cdot Y - (5+2) \cdot X = 3 \cdot 2$:

$$X = \frac{(p-1)^3 \cdot Y - (p+1)}{p}. \qquad (23)$$

**Step 3:** Exists an integer $Y = -1$ such that $X$ in the **Step 2** is an integer.

**Step 4:** We solve $x, y$ the **Step 1** using $X = -11, Y = -1$ from **Step 2**, obtain two particular solutions, let's say $x_0 = -13$ and $y_0 = 25$ of the Linear Diophantine Equation (EDL).

$$238 \cdot (-13) + 125 \cdot 25 = -3094 + 3125 = 31. \qquad (24)$$

**Step 5:** The general solution of the Linear Diophantine Equation (EDL).

$$238 \cdot x + 125 \cdot y = 31. \qquad (25)$$

is

$$x = -13 + 125 \cdot t. \qquad (26)$$

$$y = 25 - 238 \cdot t. \qquad (26)$$

where $t \in \mathbb{Z}$.

If $t = 1$, then $x = 112, y = -213$ and $238 \cdot x + 125 \cdot y = 238 \cdot 112 + 125 \cdot (-213) = 26656 - 26625 = 31$, if $t = -1$, then $x = -138, y = 263$ and $238 \cdot x + 125 \cdot y = 238 \cdot (-138) + 125 \cdot 263 = 31$.

$$\bullet 16000003120000202400004366 \cdot x + 8000001560000101400002197 \cdot y = 20000003200000127$$

**Step 1:** Using the previous theorem (2.1) we have that:

$$X = 100000008 + 2 \cdot x. \qquad (27)$$

$$Y = y + 2 \cdot x. \qquad (27)$$

Rewriting the equation

$$16000003120000202400004366 \cdot x + 8000001560000101400002197 \cdot y = 20000003200000127. \qquad (28)$$

$$8000001560000101400002197 \cdot y = 20000003200000127.$$
We obtain

$$ 
\begin{aligned}
& 8000001560000101400002197 \cdot (y + 2 \cdot x) - \\
& 200000014 \cdot (100000008 + 2 \cdot x) = 20000003200000127.
\end{aligned} 
\quad (29) 
$$

Simplify

$$ 
\begin{aligned}
& ((2 \cdot 100000007) - 1)^3 \cdot (y + 2 \cdot x) \cdot y - \\
& (2 \cdot 100000007) \cdot (100000008 + 2 \cdot x) = ((2 \cdot 100000007) + 1).
\end{aligned} 
\quad (30) 
$$

where $p = p_1 \cdot p_2$ an $p_1 = 2$, $p_2 = 100000007$, that is

$$ (2 \cdot 100000007 - 1)^3 \cdot Y - (2 \cdot 100000007) \cdot X = ((2 \cdot 100000007) + 1). \quad (31) $$

**Step 2:** In **Step 1**, we solve $X$ of equation (30):

$$ X = \frac{((2 \cdot 100000007) - 1)^3 \cdot Y - (2 \cdot 100000007)}{100000007}. \quad (32) $$

**Step 3:** If $Y = -1$ then $X$ in the **Step 2** is an integer, that is $X = -40000005000000158$.

**Step 4:** We solve $x, y$ the **Step 1** using $X = -40000005000000158$, $Y = -1$ from **Step 2** and **Step 3**, obtain two particular solutions, let's say $x_0 = -20000002550000083$ and $y_0 = 40000005100000165$ of the Linear Diophantine Equation (EDL).

$$ 
\begin{aligned}
& 16000003120000202400004366 \cdot x + \\
& 8000001560000101400002197 \cdot y = \\
& 16000003120000202400004366 \cdot (-20000002550000083) + \\
& 8000001560000101400002197 \cdot (40000005100000165) = \\
& -320000103200013332000862400027932500362378 + \\
& 320000103200013332000862420027935700362505 = \\
& 20000003200000127.
\end{aligned} 
\quad (33) 
$$

**Step 5:** The general solution of the Linear Diophantine Equation (EDL).

$$ 
\begin{aligned}
& 16000003120000202400004366 \cdot x + \\
& 8000001560000101400002197 \cdot y = 20000003200000127.
\end{aligned} 
\quad (34) 
$$

is

$$ x = -20000002550000083 + 8000001560000101400002197 \quad (35) $$

$$ y = 40000005100000165 - 16000003120000202400004366 \cdot t. $$

where $t \in \mathbb{Z}$.
If $t = 1$, and $x = 8000001540000098850002114$, $y = -1600000272000015140000271$ then

$$ 
\begin{aligned}
& 16000003120000202400004366 \cdot x + \\
& 8000001560000101400002197 \cdot y = \\
& 16000003120000202400004366 \cdot (8000001540000098850002114) + \\
& 8000001560000101400002197 \cdot (-1600000272000015140000271) = \\
& 8000001540000098850002114 + (-1600000272000015140000271) = \\
& 20000003200000127.
\end{aligned}
\quad (36) $$

### 3 Conclusion and future directions

In conclusion we can mention that this is a new approach to calculate the linear Diophantine equations (SDLE) that can be programmed in a computational algorithm, it is of our interest to see the formulation when the fixed integer is different from $-1$, that is, $Y \neq -1$, We are also interested in an approach for a system of linear and nonlinear diophantine equations and review that other types of diophantine equations can obtain the algebraic solution in a general way as well as its extension for arithmetic functions.

### References

[1] Mordell, L. J, *Diophantine equations*, Pure and Applied Mathematics (Academic Press), Pure Appl. Math., Academic Press, ISSN 0079-8169, Vol. 30, 1969, Academic Press, New York, NY, zbMATH 3300651, https://zbmath.org/0188.34503

[2] Smart N. P, *The Algorithmic Resolution of Diophantine Equations: A Computational Cookbook*, Cambridge, London Mathematical Society Student Texts, Cambridge University Press, 1998, London Mathematical Society Student Texts.

[3] Schmidt, W. M, *Diophantine approximation by numbers of small height*, Number theory and applications. Proceedings of the international conferences on number theory and cryptography, Allahabad, India, December 2006 and February 2007, ISBN 978-81-85931-97-5, 213–218, 2009, New Delhi: Hindustan Book Agency, zbMATH = 6009965, https://zbmath.org/1238.11072

SAMUEL FLORES
DEPARTMENT OF MATHEMATICS,
UNIVERSITY OF CARABOBO,
EXPERIMENTAL FACULTY OF SCIENCE AND TECHNOLOGY (FACYT), VALENCIA, VENEZUELA

Email address: sflores4@uc.edu.ve, neuromaticks@gmail.com