Sage has extensive functionality for number theory. For example, we can do arithmetic in Z/NZ as follows:
sage: R = IntegerModRing(97) sage: a = R(2) / R(3) sage: a 33 sage: a.rational_reconstruction() 2/3 sage: b = R(47) sage: b^20052005 50 sage: b.modulus() 97 sage: b.is_square() True
Sage contains standard number theoretic functions. For example,
sage: gcd(515,2005) 5 sage: factor(2005) 5 * 401 sage: c = factorial(25); c 15511210043330985984000000 sage: [valuation(c,p) for p in prime_range(2,23)] [22, 10, 6, 3, 2, 1, 1, 1] sage: next_prime(2005) 2011 sage: previous_prime(2005) 2003 sage: divisors(28); sum(divisors(28)); 2*28 [1, 2, 4, 7, 14, 28] 56 56
Sage's sigma(n,k)
function adds up the k
th powers of
the divisors of n
:
sage: sigma(28,0); sigma(28,1); sigma(28,2) 6 56 1050
We next illustrate the extended Euclidean algorithm, Euler's φ-function, and the Chinese remainder theorem:
sage: d,u,v = xgcd(12,15) sage: d == u*12 + v*15 True sage: n = 2005 sage: inverse_mod(3,n) 1337 sage: 3 * 1337 4011 sage: prime_divisors(n) [5, 401] sage: phi = n*prod([1 - 1/p for p in prime_divisors(n)]); phi 1600 sage: euler_phi(n) 1600 sage: prime_to_m_part(n, 5) 401
We next verify something about the 3n+1 problem.
sage: n = 2005 sage: for i in range(1000): n = 3*odd_part(n) + 1 if odd_part(n)==1: print i break 38
Finally we illustrate the Chinese remainder theorem.
sage: x = crt(2, 1, 3, 5); x 11 sage: x % 3 # x mod 3 = 2 2 sage: x % 5 # x mod 5 = 1 1 sage: [binomial(13,m) for m in range(14)] [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] sage: [binomial(13,m)%2 for m in range(14)] [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1] sage: [kronecker(m,13) for m in range(1,13)] [1, -1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1] sage: n = 10000; sum([moebius(m) for m in range(1,n)]) -23 sage: list(partitions(4)) [(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3), (4,)]