number theory 1

143 days ago by voloch

# sage docs for basic number theory http://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html #gcd print gcd(5,13) # extended gcd solves ax+by = gcd(a,b) print xgcd(5,13) 
       
1
(1, -5, 2)
1
(1, -5, 2)
a = 5 b = 13 d = xgcd(5,13) print d[0] print a*d[1]+ b*d[2] 
       
1
1
1
1
#Chinese remainder theorem crt(a,b,m,n) finds x = a mod m, x = b mod n print crt(1,2,5,13) 
       
41
41
#Legendre symbol print legendre_symbol(2,7) #Raising to powers mod m in a clever way. Important if numbers are big print power_mod(2,3,7) sqrt(Mod(2,7)) 
       
1
1
3
1
1
3
#loop over primes for p in primes(3,20): if legendre_symbol(2,p) == 1: print p 
       
7
17
7
17