#
# example number theory functions
# Author: Burton Rosenberg
# Date: 29 February 2008
#

def gcd(a,b):
    # ! a>=b>-1
    if b==0:
        return a
    return gcd(b,a%b)

def xgcdaux(a,b):
    if b[0]==0:
        return a
    else:
        q = a[0]/b[0]
        r = a[0]%b[0]
        return xgcdaux(b,(r,a[1]-q*b[1],a[2]-q*b[2]))

def xgcd(a,b):
    # ! a>=b>-1
    return xgcdaux((a,1,0),(b,0,1))

def modinv(x,n):
    j = xgcd(n,x%n)
    if j[0]!=1 :
        return 0
    return j[2]%n
    
def modpow(x,i,p):
    # ! i>=0
    if i==0:
	return 1
    if (i%2)==0:
	y = modpow(x,i/2,p)
	return (y*y)%p
    return (x*modpow(x,i-1,p))%p

def legendresymbol(x,p):
    return modpow(x,(p-1)/2,p)

def gen(x,p):
    y=1
    for i in range(p-1):
	y = (y*x)%p
	print y

def allquadchar(p):
    for i in range(1,p):
        print legendresymbol(i,p)

print "loaded"

# end programs