Number Theory - Tutorial (original) (raw)

Sage has extensive functionality for number theory. For example, we can do arithmetic in \(\ZZ/N\ZZ\) as follows:

Sage

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

Python

from sage.all import * R = IntegerModRing(Integer(97)) a = R(Integer(2)) / R(Integer(3)) a 33 a.rational_reconstruction() 2/3 b = R(Integer(47)) b**Integer(20052005) 50 b.modulus() 97 b.is_square() True

Sage contains standard number theoretic functions. For example,

Sage

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

Python

from sage.all import * gcd(Integer(515),Integer(2005)) 5 factor(Integer(2005)) 5 * 401 c = factorial(Integer(25)); c 15511210043330985984000000 [valuation(c,p) for p in prime_range(Integer(2),Integer(23))] [22, 10, 6, 3, 2, 1, 1, 1] next_prime(Integer(2005)) 2011 previous_prime(Integer(2005)) 2003 divisors(Integer(28)); sum(divisors(Integer(28))); Integer(2)*Integer(28) [1, 2, 4, 7, 14, 28] 56 56

Perfect!

Sage’s sigma(n,k) function adds up the \(k^{th}\) powers of the divisors of n:

Sage

sage: sigma(28,0); sigma(28,1); sigma(28,2) 6 56 1050

Python

from sage.all import * sigma(Integer(28),Integer(0)); sigma(Integer(28),Integer(1)); sigma(Integer(28),Integer(2)) 6 56 1050

We next illustrate the extended Euclidean algorithm, Euler’s\(\phi\)-function, and the Chinese remainder theorem:

Sage

sage: d,u,v = xgcd(12,15) sage: d == u12 + v15 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

Python

from sage.all import * d,u,v = xgcd(Integer(12),Integer(15)) d == uInteger(12) + vInteger(15) True n = Integer(2005) inverse_mod(Integer(3),n) 1337 Integer(3) * Integer(1337) 4011 prime_divisors(n) [5, 401] phi = n*prod([Integer(1) - Integer(1)/p for p in prime_divisors(n)]); phi 1600 euler_phi(n) 1600 prime_to_m_part(n, Integer(5)) 401

We next verify something about the \(3n+1\) problem.

Sage

sage: n = 2005 sage: for i in range(1000): ....: n = 3*odd_part(n) + 1 ....: if odd_part(n)==1: ....: print(i) ....: break 38

Python

from sage.all import * n = Integer(2005) for i in range(Integer(1000)): ... n = Integer(3)*odd_part(n) + Integer(1) ... if odd_part(n)==Integer(1): ... print(i) ... break 38

Finally we illustrate the Chinese remainder theorem.

Sage

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: Partitions(4).list() [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

Python

from sage.all import * x = crt(Integer(2), Integer(1), Integer(3), Integer(5)); x 11 x % Integer(3) # x mod 3 = 2 2 x % Integer(5) # x mod 5 = 1 1 [binomial(Integer(13),m) for m in range(Integer(14))] [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] [binomial(Integer(13),m)%Integer(2) for m in range(Integer(14))] [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1] [kronecker(m,Integer(13)) for m in range(Integer(1),Integer(13))] [1, -1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1] n = Integer(10000); sum([moebius(m) for m in range(Integer(1),n)]) -23 Partitions(Integer(4)).list() [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

\(p\)-adic Numbers

The field of \(p\)-adic numbers is implemented in Sage. Note that once a \(p\)-adic field is created, you cannot change its precision.

Sage

sage: K = Qp(11); K 11-adic Field with capped relative precision 20 sage: a = K(211/17); a 4 + 411 + 11^2 + 711^3 + 911^5 + 511^6 + 411^7 + 811^8 + 7*11^9

Python

from sage.all import * K = Qp(Integer(11)); K 11-adic Field with capped relative precision 20 a = K(Integer(211)/Integer(17)); a 4 + 411 + 11^2 + 711^3 + 911^5 + 511^6 + 411^7 + 811^8 + 7*11^9

Much work has been done implementing rings of integers in\(p\)-adic fields and number fields. The interested reader is invited to read[Introduction to the p-adics](../reference/padics/sage/rings/padics/tutorial.html#sage-rings-padics-tutorial "(in ppp-adics v10.8)") and ask the experts on thesage-support Google group for further details.

A number of related methods are already implemented in the NumberField class.

Sage

sage: R. = PolynomialRing(QQ) sage: K = NumberField(x^3 + x^2 - 2x + 8, 'a') sage: K.integral_basis() [1, 1/2a^2 + 1/2*a, a^2]

Python

from sage.all import * R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1) K = NumberField(xInteger(3) + xInteger(2) - Integer(2)x + Integer(8), 'a') K.integral_basis() [1, 1/2a^2 + 1/2*a, a^2]

Sage

sage: K.galois_group() Galois group 3T2 (S3) with order 6 of x^3 + x^2 - 2*x + 8

Python

from sage.all import * K.galois_group() Galois group 3T2 (S3) with order 6 of x^3 + x^2 - 2*x + 8

Sage

sage: K.polynomial_quotient_ring() Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^3 + x^2 - 2x + 8 sage: K.units() (-3a^2 - 13a - 13,) sage: K.discriminant() -503 sage: K.class_group() Class group of order 1 of Number Field in a with defining polynomial x^3 + x^2 - 2x + 8 sage: K.class_number() 1

Python

from sage.all import * K.polynomial_quotient_ring() Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^3 + x^2 - 2x + 8 K.units() (-3a^2 - 13a - 13,) K.discriminant() -503 K.class_group() Class group of order 1 of Number Field in a with defining polynomial x^3 + x^2 - 2x + 8 K.class_number() 1