.. 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_02_pell_equation.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_02_pell_equation.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_number_theory_diophantine_plot_02_pell_equation.py:


Pell's equation x^2 - Dy^2 = 1
===================================================

Fermat's 1657 challenge: solve :math:`x^2 - Dy^2 = 1` in integers. The
continued fraction of :math:`\sqrt D` always yields the fundamental
solution (Lagrange, 1768), but its size is wildly erratic -- for
:math:`D = 61` it is :math:`x = 1766319049`, while :math:`D = 60` needs
only :math:`x = 31`. This script reproduces Fermat's :math:`D = 61`
case, generates further solutions from the fundamental one, and plots
the fundamental :math:`x` for every non-square :math:`D \le 120`.

.. GENERATED FROM PYTHON SOURCE LINES 15-21

.. code-block:: Python

    import math

    import matplotlib.pyplot as plt

    from mathematicskit.number_theory import solve_pell_equation








.. GENERATED FROM PYTHON SOURCE LINES 22-24

Fermat's challenge: D = 61
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 24-29

.. code-block:: Python


    pell = solve_pell_equation(61)
    print(f"fundamental solution of x^2 - 61y^2 = 1: x={pell.x}, y={pell.y}")
    print(f"check: x^2 - 61y^2 = {pell.x**2 - 61 * pell.y**2}")





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

 .. code-block:: none

    fundamental solution of x^2 - 61y^2 = 1: x=1766319049, y=226153980
    check: x^2 - 61y^2 = 1




.. GENERATED FROM PYTHON SOURCE LINES 30-33

Every solution is a power of the fundamental one
-----------------------------------------------------
:math:`x_k + y_k\sqrt D = (x_1 + y_1\sqrt D)^k`.

.. GENERATED FROM PYTHON SOURCE LINES 33-39

.. code-block:: Python


    x, y = pell.x, pell.y
    for k in range(2, 4):
        x, y = x * pell.x + 61 * y * pell.y, x * pell.y + y * pell.x
        print(f"  k={k}: x has {len(str(x))} digits, x^2 - 61y^2 = {x * x - 61 * y * y}")





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

 .. code-block:: none

      k=2: x has 19 digits, x^2 - 61y^2 = 1
      k=3: x has 29 digits, x^2 - 61y^2 = 1




.. GENERATED FROM PYTHON SOURCE LINES 40-42

The fundamental solution's size jumps around with D
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 42-54

.. code-block:: Python


    ds = [d for d in range(2, 121) if math.isqrt(d) ** 2 != d]
    xs = [solve_pell_equation(d).x for d in ds]

    fig, ax = plt.subplots()
    ax.semilogy(ds, xs, "o", ms=4)
    ax.semilogy([61], [pell.x], "o", ms=9, mfc="none", mec="red", label="D = 61 (Fermat, 1657)")
    ax.set_xlabel("D")
    ax.set_ylabel("fundamental x")
    ax.set_title("Smallest solution of Pell's equation x^2 - Dy^2 = 1")
    ax.legend()
    plt.show()



.. image-sg:: /api/gallery/number_theory/diophantine/images/sphx_glr_plot_02_pell_equation_001.png
   :alt: Smallest solution of Pell's equation x^2 - Dy^2 = 1
   :srcset: /api/gallery/number_theory/diophantine/images/sphx_glr_plot_02_pell_equation_001.png
   :class: sphx-glr-single-img






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

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


.. _sphx_glr_download_api_gallery_number_theory_diophantine_plot_02_pell_equation.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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