SM-5-Exercise9

#Giving names to the set of integers and primes NN=NonNegativeIntegers() P=Primes() 

#Given a an integer p, returns the smallest integer a such that p=a^2+b^2 and a=1(mod p) if p in prime or else returns 0 def a(p): if p in P and p%4==1: outout=0 a=1 while(a^2<p): if sqrt(p-a^2) in NN: outout=sqrt(p-a^2) break else: a=a+4 if outout!=0: return a else: return 0 else: return 0 

#Makes a list of pairs (p,a) for p up to 4N-3 def ListPair(N): l=[] for j in range(N): p=4*j+1 if a(p)!=0: l.append((p,a(p))) return l 

# Creates the Gaussian factorial N_n! # You might want to combine this and the next function mod p (less robustly) so it returns answers more quickly def GaussFactorial(N,n): prod=1 for j in range(1,N+1): if GCD(j,n)==1: prod=prod*j return prod 

#Creates Central Binomial Coefficient B_4(p,alpha) def B_4(p, alpha): N=(p^alpha-1)/2 D=N/2 return GaussFactorial(N,p)/(GaussFactorial(D,p))^2 

#Finally... #Checks the first identity for primes up to 4*N-3 def CheckIdentity1(N): L=ListPair(N) length=len(L) l=[] for j in range(length): p=L[j][0] a=L[j][1] l.append(B_4(p,1)%p == 2*a) return l 

#Checking first identity up to about 400 CheckIdentity1(100) 

[True, True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True]

[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]

#Checks the second identity for primes up to 4*N-3 def CheckIdentity2(N): L=ListPair(N) length=len(L) l=[] for j in range(length): p=L[j][0] a=L[j][1] l.append(B_4(p,2)%p == (2*a-p*(2*a).inverse_mod(p))%p) return l 

#Checking second identity up to 200 CheckIdentity2(50) 

[True, True, True, True, True, True, True, True, True, True, True, True]

[True, True, True, True, True, True, True, True, True, True, True, True]