.. _sphx_glr_api_gallery_number_theory_crt:

Chinese Remainder Theorem
----------------------------

Combining congruences with pairwise-coprime moduli.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="The 3rd-5th-century Chinese text Sunzi Suanjing poses: &quot;There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; by 7 the remainder is 2. What is the number?&quot; -- the original problem the Chinese Remainder Theorem is named for.">

.. only:: html

  .. image:: /api/gallery/number_theory/crt/images/thumb/sphx_glr_plot_01_sunzi_problem_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/crt/plot_01_sunzi_problem`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Sunzi's classic "remainder problem"</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Gauss&#x27;s Disquisitiones Arithmeticae (1801) opens by defining a \equiv b \pmod m and computing with residues instead of numbers. Its Articles 32-36 prove that congruences with pairwise coprime moduli combine into one: working modulo m_1 m_2 is the same as working modulo m_1 and m_2 at once. This script checks Gauss&#x27;s rules of congruence arithmetic, draws the residue grid that pairs each class mod 35 with one class mod 5 and one mod 7, and reduces a huge power with fast modular exponentiation.">

.. only:: html

  .. image:: /api/gallery/number_theory/crt/images/thumb/sphx_glr_plot_02_gauss_congruences_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/crt/plot_02_gauss_congruences`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Gauss's Disquisitiones: congruences and the remainder theorem</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/crt/plot_01_sunzi_problem
   /api/gallery/number_theory/crt/plot_02_gauss_congruences