maths.modular_division
======================

.. py:module:: maths.modular_division


Functions
---------

.. autoapisummary::

   maths.modular_division.extended_euclid
   maths.modular_division.extended_gcd
   maths.modular_division.greatest_common_divisor
   maths.modular_division.invert_modulo
   maths.modular_division.modular_division
   maths.modular_division.modular_division2


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

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

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

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



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

   Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers x
   and y, then d = gcd(a,b)
   >>> extended_gcd(10, 6)
   (2, -1, 2)

   >>> extended_gcd(7, 5)
   (1, -2, 3)

   ** extended_gcd function is used when d = gcd(a,b) is required in output



.. py:function:: greatest_common_divisor(a: int, b: int) -> int

   Euclid's Lemma :  d divides a and b, if and only if d divides a-b and b
   Euclid's Algorithm

   >>> greatest_common_divisor(7,5)
   1

   Note : In number theory, two integers a and b are said to be relatively prime,
       mutually prime, or co-prime if the only positive integer (factor) that divides
       both of them is 1  i.e., gcd(a,b) = 1.

   >>> greatest_common_divisor(121, 11)
   11



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

   This function find the inverses of a i.e., a^(-1)

   >>> invert_modulo(2, 5)
   3

   >>> invert_modulo(8,7)
   1



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

   Modular Division :
   An efficient algorithm for dividing b by a modulo n.

   GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )

   Given three integers a, b, and n, such that gcd(a,n)=1 and n>1, the algorithm should
   return an integer x such that 0≤x≤n-1, and  b/a=x(modn) (that is, b=ax(modn)).

   Theorem:
   a has a multiplicative inverse modulo n iff gcd(a,n) = 1


   This find x = b*a^(-1) mod n
   Uses ExtendedEuclid to find the inverse of a

   >>> modular_division(4,8,5)
   2

   >>> modular_division(3,8,5)
   1

   >>> modular_division(4, 11, 5)
   4



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

   This function used the above inversion of a to find x = (b*a^(-1))mod n

   >>> modular_division2(4,8,5)
   2

   >>> modular_division2(3,8,5)
   1

   >>> modular_division2(4, 11, 5)
   4