.. _sphx_glr_api_gallery_number_theory_totient:

Multiplicative functions
--------------------------

Euler's totient function, the Mobius function, and divisor sums.


.. 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="Euler&#x27;s \varphi(n) counts the integers in 1, \dots, n coprime to n. His 1763 theorem, a^{\varphi(n)} \equiv 1 \pmod n for \gcd(a, n) = 1, generalizes Fermat&#x27;s little theorem (\varphi(p) = p - 1 for a prime p). This script checks the definition and the theorem and plots \varphi(n), whose top edge n - 1 is traced by the primes.">

.. only:: html

  .. image:: /api/gallery/number_theory/totient/images/thumb/sphx_glr_plot_01_euler_totient_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/totient/plot_01_euler_totient`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Euler's totient function and Euler's theorem</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A perfect number equals the sum of its own proper divisors (\sigma(n) = 2n). This script finds the perfect numbers below 10,000 with divisor_sum and checks Euclid&#x27;s form 2^{p-1}(2^p - 1) for each.">

.. only:: html

  .. image:: /api/gallery/number_theory/totient/images/thumb/sphx_glr_plot_02_perfect_numbers_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/totient/plot_02_perfect_numbers`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Perfect numbers and the divisor-sum function</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/totient/plot_01_euler_totient
   /api/gallery/number_theory/totient/plot_02_perfect_numbers