
'''simple docstring'''







from __future__ import annotations
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				Any   ,   __SCREAMING_SNAKE_CASE      :				Tuple   ,   __SCREAMING_SNAKE_CASE      :				List[str]							):



						"""simple docstring"""





						assert n > 1 and a > 0 and greatest_common_divisor(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE							) == 1
						(lowercase_)			:  List[str]									= extended_gcd(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE							)  # Implemented below
						lowercase_			:  Union[str, Any]									= (b * s) % n
						return x
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				str   ,   __SCREAMING_SNAKE_CASE      :				Dict							):



						"""simple docstring"""





						(lowercase_)			:  List[str]									= extended_euclid(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE							)  # Implemented below
						if b < 0:
												lowercase_			:  List[str]									= (b % n + n) % n
						return b
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				int   ,   __SCREAMING_SNAKE_CASE      :				Tuple   ,   __SCREAMING_SNAKE_CASE      :				Any							):



						"""simple docstring"""





						lowercase_			:  Tuple									= invert_modulo(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE							)
						lowercase_			:  Any									= (b * s) % n
						return x
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				List[Any]   ,   __SCREAMING_SNAKE_CASE      :				str							):



						"""simple docstring"""





						assert a >= 0 and b >= 0

						if b == 0:
												lowercase_			:  Union[str, Any]									= a, 1, 0
						else:
												(lowercase_)			:  Tuple									= extended_gcd(__SCREAMING_SNAKE_CASE   ,   a % b							)
												lowercase_			:  int									= q
												lowercase_			:  Any									= p - q * (a // b)

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

						return (d, x, y)
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				List[str]   ,   __SCREAMING_SNAKE_CASE      :				Tuple							):



						"""simple docstring"""





						if b == 0:
												return (1, 0)
						(lowercase_)			:  int									= extended_euclid(__SCREAMING_SNAKE_CASE   ,   a % b							)
						lowercase_			:  List[Any]									= a // b
						return (y, x - k * y)
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				Tuple   ,   __SCREAMING_SNAKE_CASE      :				Any							):



						"""simple docstring"""





						if a < b:
												lowercase_			:  Union[str, Any]									= b, a

						while a % b != 0:
												lowercase_			:  Optional[int]									= 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)





'''simple docstring'''







import math
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				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(__SCREAMING_SNAKE_CASE							) + 1							)   ,   6							):
												if number % i == 0 or number % (i + 2) == 0:
																		return False
						return True
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				int = 600851475143							):



						"""simple docstring"""





						try:
												lowercase_			:  List[str]									= int(__SCREAMING_SNAKE_CASE							)
						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.'''							)
						lowercase_			:  Tuple									= 0
						if is_prime(__SCREAMING_SNAKE_CASE							):
												return n
						while n % 2 == 0:
												n //= 2
						if is_prime(__SCREAMING_SNAKE_CASE							):
												return n
						for i in range(3   ,   int(math.sqrt(__SCREAMING_SNAKE_CASE							)							) + 1   ,   2							):
												if n % i == 0:
																		if is_prime(n // i							):
																								lowercase_			:  str									= n // i
																								break
																		elif is_prime(__SCREAMING_SNAKE_CASE							):
																								lowercase_			:  Optional[Any]									= i
						return max_number


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



