





'''simple docstring'''







from __future__ import annotations

def    __UpperCamelCase	(	a    : Tuple					,   a    : Union[str, Any]     ) ->Tuple:
 if b == 0:
  return (1, 0)
 (snake_case)				=			extended_euclid(snake_case_					,   a % b     )
 snake_case				=			a // b
 return (y, x - k * y)

def    __UpperCamelCase	(	a    : Dict					,   a    : Any					,   a    : List[Any]					,   a    : Tuple     ) ->Tuple:
 (snake_case)				=			extended_euclid(snake_case_					,   snake_case_     )
 snake_case				=			na * na
 snake_case				=			ra * x * na + ra * y * na
 return (n % m + m) % m

def    __UpperCamelCase	(	a    : Tuple					,   a    : int     ) ->int:
 (snake_case)				=			extended_euclid(snake_case_					,   snake_case_     )
 if b < 0:
  snake_case				=			(b % n + n) % n
 return b

def    __UpperCamelCase	(	a    : Union[str, Any]					,   a    : Optional[int]					,   a    : Any					,   a    : int     ) ->List[str]:
 snake_case				=			invert_modulo(snake_case_					,   snake_case_     ), invert_modulo(snake_case_					,   snake_case_     )
 snake_case				=			na * na
 snake_case				=			ra * x * na + ra * y * na
 return (n % m + m) % m


if __name__ == "__main__":
      from doctest import testmod

      testmod(name='chinese_remainder_theorem', verbose=True)
      testmod(name='chinese_remainder_theorem2', verbose=True)
      testmod(name='invert_modulo', verbose=True)
      testmod(name='extended_euclid', verbose=True)








'''simple docstring'''







def    __UpperCamelCase	(	a    : int					,   a    : int     ) ->int:
 while b:
  snake_case				,		snake_case				=			b, a % b
 return a

def    __UpperCamelCase	(	a    : int					,   a    : int     ) ->int:
 return a if b == 0 else euclidean_gcd_recursive(a					,   a % b     )

def    __UpperCamelCase	(	) ->Optional[Any]:
 print(f"""euclidean_gcd(3, 5) = {euclidean_gcd(3					,   5     )}"""     )
 print(f"""euclidean_gcd(5, 3) = {euclidean_gcd(5					,   3     )}"""     )
 print(f"""euclidean_gcd(1, 3) = {euclidean_gcd(1					,   3     )}"""     )
 print(f"""euclidean_gcd(3, 6) = {euclidean_gcd(3					,   6     )}"""     )
 print(f"""euclidean_gcd(6, 3) = {euclidean_gcd(6					,   3     )}"""     )

 print(f"""euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3					,   5     )}"""     )
 print(f"""euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5					,   3     )}"""     )
 print(f"""euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1					,   3     )}"""     )
 print(f"""euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3					,   6     )}"""     )
 print(f"""euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6					,   3     )}"""     )


if __name__ == "__main__":
   main()

