maths.chinese_remainder_theorem
===============================

.. py:module:: maths.chinese_remainder_theorem

.. autoapi-nested-parse::

   Chinese Remainder Theorem:
   GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )

   If GCD(a,b) = 1, then for any remainder ra modulo a and any remainder rb modulo b
   there exists integer n, such that n = ra (mod a) and n = ra(mod b).  If n1 and n2 are
   two such integers, then n1=n2(mod ab)

   Algorithm :

   1. Use extended euclid algorithm to find x,y such that a*x + b*y = 1
   2. Take n = ra*by + rb*ax



Functions
---------

.. autoapisummary::

   maths.chinese_remainder_theorem.chinese_remainder_theorem
   maths.chinese_remainder_theorem.chinese_remainder_theorem2
   maths.chinese_remainder_theorem.extended_euclid
   maths.chinese_remainder_theorem.invert_modulo


Module Contents
---------------

.. py:function:: chinese_remainder_theorem(n1: int, r1: int, n2: int, r2: int) -> int

   >>> chinese_remainder_theorem(5,1,7,3)
   31

   Explanation : 31 is the smallest number such that
               (i)  When we divide it by 5, we get remainder 1
               (ii) When we divide it by 7, we get remainder 3

   >>> chinese_remainder_theorem(6,1,4,3)
   14



.. py:function:: chinese_remainder_theorem2(n1: int, r1: int, n2: int, r2: int) -> int

   >>> chinese_remainder_theorem2(5,1,7,3)
   31

   >>> chinese_remainder_theorem2(6,1,4,3)
   14



.. py:function:: extended_euclid(a: int, b: int) -> tuple[int, int]

   >>> extended_euclid(10, 6)
   (-1, 2)

   >>> extended_euclid(7, 5)
   (-2, 3)



.. py:function:: invert_modulo(a: int, n: int) -> int

   >>> invert_modulo(2, 5)
   3

   >>> invert_modulo(8,7)
   1