```python

```

# Diophantine Equation

Goal - finding the integer solutions

$a \in \mathbb{Z}$ and $b \in \mathbb{Z}$

Then the following diophantine equation has a solution.

$a.x + b.y = gcd(a,b)$

----

Example:
47x + 30y = 1
Use Euclidean Algorithm
a / b = q + r  =>   a = b.q + r


47/30 = 1, r 17 <br/><br/>

$\begin{equation}
\begin{split}
47 &= 30(1) &+ 17  &\implies 17 &= 47(1) &+ 30(-1) \\
30 &= 17(1) &+ 13  &\implies 13 &= 30(1) &+ 17(-1) \\
17 &= 13(1) &+ 4  &\implies 4 &= 17(1) &+ 13(-1) \\
13 &= 4(3) &+ 1  &\implies 1 &= 13(1) &+ 4(-3) \\
\end{split}
\end{equation}$



$\begin{equation}
\begin{split}
1 &= 13(1) &+ 4(-3) &&\text{  substitute 4} \\
&= 13(1)   &+ \Big(17(1) &+ 13(-1)\Big)&(-3) \\
&= 13(1)   &+ 17(-3) &+ 13(3) \\
&= 17(-3)  &+ 13(4) &&\text{  substitute 13} \\
&= 17(-3)  &+ \Big( 30(1) &+ 17(-1) \Big)&(4) \\
&= 17(-3)  &+ 30(4) &+ 17(-4) \\
&= 30(4)   &+ 17(-7) &&\text{  substitute 17}\\
&= 30(4)   &+ \Big( 47(1) &+ 30(-1) \Big)&(-7) \\
&= 30(4)   &+  47(-7) &+ 30(7) \\
&= 47(-7)  &+ 30(11) \\
\end{split}
\end{equation}$

47x + 30y = 1 has a solution, x=-7, y=11




```python

```


```python

```

05843aad65ba7e50210435894c85875abdb536cb
ipynb
Jupyter Notebook
notebooks/math/number_theory/diophantine-equation.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/math/number_theory/diophantine-equation.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/math/number_theory/diophantine-equation.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
Qwen/Qwen-72B
1. YES
2. YES