import math

def totient(n):
    """
    :param n: integer to take totient of
    :return: the totient of n
             See https://en.wikipedia.org/wiki/Euler%27s_totient_function
    :author: Josiah Yoder
    """

    #def totient(n):
    totient = 0

    if n == 1:
        totient = 1
    else:
        for i in range(1, n):
            if math.gcd(i, n) == 1:
                totient += 1
    return totient

def exponent_modulus(n):
    """
    :param n: integer to take pseudo-totient of.
        a pseudo-totient z is something you can use as the modulus in the exponent:
           (m**e)%n == (m**(e%z))%n
        like we use in RSA:
            (m**(d*e))%n == (m**((d*e)%z))%n == (m**1)%n = m
        the surprising thing is that the only pseudo-totients that actually
        work for all m and e are primes!
        Even for the z = p*q we use in class, it's not actually true that
            (m**e)%n == (m**(e%z))%n
        for all m and e! (But it IS true when we need it!)

        (pseudo-totient is a term of my own making)
    :return: the pseudo-totient z for the integer n
    :author: Josiah Yoder
    """
    pseudo_totient = []
    t = totient(n)
    for z in range(1,n):
        if all((m**e)%n == (m**(e%z))%n for m in range(1,n) for e in range(1,n)):
            print("n:", n)
            print("z:", z)
            print("true totient:", t)
            print()
            pseudo_totient.append(z)
    return pseudo_totient

def find_totients(max):
    totients = dict()
    for i in range(1,max+1):
        totients[i] = totient(i)

    print('Totients:')
    for i in range(1,max+1):
        print(i,totients[i])

def find_pseudo_totients(max):
    totients = dict()
    pseudo_totients = dict()
    for i in range(1,max+1):
        totients[i] = totient(i)
        pseudo_totients[i] = exponent_modulus(i)

    print('Totients:')
    for i in range(1,max+1):
        print(i,totients[i],pseudo_totients[i])


# find_totients(1000)
find_pseudo_totients(100)