.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/number_theory/diophantine/plot_01_linear_diophantine.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_number_theory_diophantine_plot_01_linear_diophantine.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_number_theory_diophantine_plot_01_linear_diophantine.py:


Diophantus and the linear equation ax + by = c
===================================================

Diophantus's *Arithmetica* asks for whole-number solutions of equations
with more unknowns than constraints. For the linear case
:math:`ax + by = c`, integer solutions exist exactly when
:math:`\gcd(a, b)` divides :math:`c`, and then they form one infinite
family spaced evenly along the line. This script solves
:math:`12x + 18y = 30`, shows that :math:`12x + 18y = 31` has no
solution, and plots the integer points on the line.

.. GENERATED FROM PYTHON SOURCE LINES 15-20

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.number_theory import solve_linear_diophantine








.. GENERATED FROM PYTHON SOURCE LINES 21-23

Solvable: 12x + 18y = 30 (gcd 6 divides 30)
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 23-32

.. code-block:: Python


    linear = solve_linear_diophantine(12, 18, 30)
    print(f"particular solution: x={linear.x0}, y={linear.y0} (gcd={linear.gcd})")
    print(f"general solution: x = {linear.x0} + {linear.x_step}k, y = {linear.y0} - {linear.y_step}k")
    for k in range(-2, 3):
        x = linear.x0 + k * linear.x_step
        y = linear.y0 - k * linear.y_step
        print(f"  k={k:>2}: (x, y) = ({x:>3}, {y:>3}), 12x + 18y = {12 * x + 18 * y}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    particular solution: x=-5, y=5 (gcd=6)
    general solution: x = -5 + 3k, y = 5 - 2k
      k=-2: (x, y) = (-11,   9), 12x + 18y = 30
      k=-1: (x, y) = ( -8,   7), 12x + 18y = 30
      k= 0: (x, y) = ( -5,   5), 12x + 18y = 30
      k= 1: (x, y) = ( -2,   3), 12x + 18y = 30
      k= 2: (x, y) = (  1,   1), 12x + 18y = 30




.. GENERATED FROM PYTHON SOURCE LINES 33-35

Unsolvable: 12x + 18y = 31 (gcd 6 does not divide 31)
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 35-38

.. code-block:: Python


    print("12x + 18y = 31 solvable:", solve_linear_diophantine(12, 18, 31).has_solution)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    12x + 18y = 31 solvable: False




.. GENERATED FROM PYTHON SOURCE LINES 39-41

The integer solutions lie evenly spaced on the line
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 41-57

.. code-block:: Python


    ks = np.arange(-4, 5)
    xs = linear.x0 + ks * linear.x_step
    ys = linear.y0 - ks * linear.y_step
    line_x = np.linspace(xs.min() - 2, xs.max() + 2, 2)

    fig, ax = plt.subplots(figsize=(6, 5))
    gx, gy = np.meshgrid(np.arange(xs.min() - 2, xs.max() + 3), np.arange(ys.min() - 2, ys.max() + 3))
    ax.plot(gx, gy, ".", color="0.8", ms=3)
    ax.plot(line_x, (30 - 12 * line_x) / 18, "-", color="tab:blue", label="12x + 18y = 30")
    ax.plot(xs, ys, "o", color="tab:red", label="integer solutions")
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.set_title("Diophantine solutions of 12x + 18y = 30")
    ax.legend()
    plt.show()



.. image-sg:: /api/gallery/number_theory/diophantine/images/sphx_glr_plot_01_linear_diophantine_001.png
   :alt: Diophantine solutions of 12x + 18y = 30
   :srcset: /api/gallery/number_theory/diophantine/images/sphx_glr_plot_01_linear_diophantine_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.036 seconds)


.. _sphx_glr_download_api_gallery_number_theory_diophantine_plot_01_linear_diophantine.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_linear_diophantine.ipynb <plot_01_linear_diophantine.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_linear_diophantine.py <plot_01_linear_diophantine.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_linear_diophantine.zip <plot_01_linear_diophantine.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_