carmichael numbers a number n is said to be a carmichael number if it satisfies the following modular arithmetic condition powerb n1 mod n 1 for all b ranging from 1 to n such that b and n are relatively prime i e gcdb n 1 examples of carmichael numbers 561 1105 https en wikipedia orgwikicarmichaelnumber examples power2 15 3 2 power5 1 30 5 examples iscarmichaelnumber4 false iscarmichaelnumber561 true iscarmichaelnumber562 false iscarmichaelnumber900 false iscarmichaelnumber1105 true iscarmichaelnumber8911 true iscarmichaelnumber5 1 traceback most recent call last valueerror number 5 1 must instead be a positive integer iscarmichaelnumber7 traceback most recent call last valueerror number 7 must instead be a positive integer iscarmichaelnumber0 traceback most recent call last valueerror number 0 must instead be a positive integer examples power 2 15 3 2 power 5 1 30 5 examples is_carmichael_number 4 false is_carmichael_number 561 true is_carmichael_number 562 false is_carmichael_number 900 false is_carmichael_number 1105 true is_carmichael_number 8911 true is_carmichael_number 5 1 traceback most recent call last valueerror number 5 1 must instead be a positive integer is_carmichael_number 7 traceback most recent call last valueerror number 7 must instead be a positive integer is_carmichael_number 0 traceback most recent call last valueerror number 0 must instead be a positive integer
from maths.greatest_common_divisor import greatest_common_divisor


def power(x: int, y: int, mod: int) -> int:
    

    if y == 0:
        return 1
    temp = power(x, y // 2, mod) % mod
    temp = (temp * temp) % mod
    if y % 2 == 1:
        temp = (temp * x) % mod
    return temp


def is_carmichael_number(n: int) -> bool:
    

    if n <= 0 or not isinstance(n, int):
        msg = f"Number {n} must instead be a positive integer"
        raise ValueError(msg)

    return all(
        power(b, n - 1, n) == 1
        for b in range(2, n)
        if greatest_common_divisor(b, n) == 1
    )


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    number = int(input("Enter number: ").strip())
    if is_carmichael_number(number):
        print(f"{number} is a Carmichael Number.")
    else:
        print(f"{number} is not a Carmichael Number.")