
from __future__ import annotations






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			assert n > 1 and a > 0 and greatest_common_divisor(__lowerCAmelCase   ,							__lowerCAmelCase    ) == 1
			((lowerCAmelCase_)     ,  (lowerCAmelCase_)     ,  (lowerCAmelCase_))      =     extended_gcd(__lowerCAmelCase   ,							__lowerCAmelCase    )  # Implemented below
			lowerCAmelCase_      =     (b * s) % n
			return x






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			((lowerCAmelCase_)     ,  (lowerCAmelCase_))      =     extended_euclid(__lowerCAmelCase   ,							__lowerCAmelCase    )  # Implemented below
			if b < 0:
						lowerCAmelCase_      =     (b % n + n) % n
			return b






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			lowerCAmelCase_      =     invert_modulo(__lowerCAmelCase   ,							__lowerCAmelCase    )
			lowerCAmelCase_      =     (b * s) % n
			return x






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			assert a >= 0 and b >= 0

			if b == 0:
						lowerCAmelCase_     ,  lowerCAmelCase_     ,  lowerCAmelCase_      =     a, 1, 0
			else:
						((lowerCAmelCase_)     ,  (lowerCAmelCase_)     ,  (lowerCAmelCase_))      =     extended_gcd(__lowerCAmelCase   ,							a % b    )
						lowerCAmelCase_      =     q
						lowerCAmelCase_      =     p - q * (a // b)

			assert a % d == 0 and b % d == 0
			assert d == a * x + b * y

			return (d, x, y)






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			if b == 0:
						return (1, 0)
			((lowerCAmelCase_)     ,  (lowerCAmelCase_))      =     extended_euclid(__lowerCAmelCase   ,							a % b    )
			lowerCAmelCase_      =     a // b
			return (y, x - k * y)






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			if a < b:
						lowerCAmelCase_     ,  lowerCAmelCase_      =     b, a

			while a % b != 0:
						lowerCAmelCase_     ,  lowerCAmelCase_      =     b, a % b

			return b


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

			testmod(name="modular_division", verbose=True)
			testmod(name="modular_division2", verbose=True)
			testmod(name="invert_modulo", verbose=True)
			testmod(name="extended_gcd", verbose=True)
			testmod(name="extended_euclid", verbose=True)
			testmod(name="greatest_common_divisor", verbose=True)





import math






def        lowerCamelCase__    (    __lowerCAmelCase  :  int    ):




			"""simple docstring"""


			if 1 < number < 4:
						# 2 and 3 are primes
						return True
			elif number < 2 or number % 2 == 0 or number % 3 == 0:
						# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
						return False

			# All primes number are in format of 6k +/- 1
			for i in range(5   ,							int(math.sqrt(__lowerCAmelCase    ) + 1    )   ,							6    ):
						if number % i == 0 or number % (i + 2) == 0:
									return False
			return True






def        lowerCamelCase__    (    __lowerCAmelCase  :  int = 600851475143    ):




			"""simple docstring"""


			try:
						lowerCAmelCase_      =     int(__lowerCAmelCase    )
			except (TypeError, ValueError):
						raise TypeError("Parameter n must be int or castable to int."    )
			if n <= 0:
						raise ValueError("Parameter n must be greater than or equal to one."    )
			lowerCAmelCase_      =     0
			if is_prime(__lowerCAmelCase    ):
						return n
			while n % 2 == 0:
						n //= 2
			if is_prime(__lowerCAmelCase    ):
						return n
			for i in range(3   ,							int(math.sqrt(__lowerCAmelCase    )    ) + 1   ,							2    ):
						if n % i == 0:
									if is_prime(n // i    ):
												lowerCAmelCase_      =     n // i
												break
									elif is_prime(__lowerCAmelCase    ):
												lowerCAmelCase_      =     i
			return max_number


if __name__ == "__main__":
			print(f"""{solution() = }""")



