N = 37 * 31
a = 29
print(N)

import math
math.gcd(a, N)

import matplotlib.pyplot as plt

z = range(N)
y = [a**z0 % N for z0 in z]
plt.plot(z, y)
plt.xlabel('z')
plt.ylabel('{}^z mod {}'.format(a, N))
plt.show()

r = y[1:].index(1)+1
print(r)

if r%2 == 0:
    x = (a**(r//2)) % N
    print('x = {}'.format(x))
    if ((x+1)%N) != 0:
        print(math.gcd(int(x)+1, N), math.gcd(int(x)-1, N))
    else:
        print('x+1 % N = 0')
else:
    print('r = {} is odd'.format(r))