Skip to content

linear-diophantine: add Bézout's lemma and slightly reformat mathjax #1358

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Oct 15, 2024
Merged

linear-diophantine: add Bézout's lemma and slightly reformat mathjax #1358

Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
0e9d69b
linear-diophantine: add Bézout's lemma and slightly reformat mathjax
jxu Oct 14, 2024
5617b11
linear-diophantine: move identity
jxu Oct 14, 2024
b1ba599
linear-diophantine: reword Bézout and explain all solutions
jxu Oct 14, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
16 changes: 11 additions & 5 deletions src/algebra/linear-diophantine-equation.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,10 +27,10 @@ A degenerate case that need to be taken care of is when $a = b = 0$. It is easy

When $a \neq 0$ and $b \neq 0$, the equation $ax+by=c$ can be equivalently treated as either of the following:

\begin{gather}
ax \equiv c \pmod b,\newline
by \equiv c \pmod a.
\end{gather}
\begin{align}
ax &\equiv c \pmod b \\
by &\equiv c \pmod a
\end{align}

Without loss of generality, assume that $b \neq 0$ and consider the first equation. When $a$ and $b$ are co-prime, the solution to it is given as

Expand All @@ -51,6 +51,12 @@ y = \frac{c-ax}{b}.

## Algorithmic solution

**Bézout's lemma** (also called Bézout's identity) is a useful result that can be used to understand the following solution.

> Let $g = \gcd(a,b)$. Then there exist integers $x,y$ such that $ax + by = g$.
>
> Moreover, $g$ is the least such positive integer that can be written as $ax + by$; all integers of the form $ax + by$ are multiples of $g$.

To find one solution of the Diophantine equation with 2 unknowns, you can use the [Extended Euclidean algorithm](extended-euclid-algorithm.md). First, assume that $a$ and $b$ are non-negative. When we apply Extended Euclidean algorithm for $a$ and $b$, we can find their greatest common divisor $g$ and 2 numbers $x_g$ and $y_g$ such that:

$$a x_g + b y_g = g$$
Expand Down Expand Up @@ -119,7 +125,7 @@ $$y = y_0 - k \cdot \frac{a}{g}$$

are solutions of the given Diophantine equation.

Moreover, this is the set of all possible solutions of the given Diophantine equation.
Since the equation is linear, all solutions lie on the same line, and by the definition of $g$ this is the set of all possible solutions of the given Diophantine equation.

## Finding the number of solutions and the solutions in a given interval

Expand Down
Loading