Sage Quick Reference: Elementary Number Theory William Stein (modified by nu) Sage Version 3.4

         http://wiki.sagemath.org/quickref

GNU Free Document License, extend for your own use

Everywhere m, n, a, b, etc. are elements of ZZ ZZ = ℤ = all integers

Integers

…, −2, −1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …

n divided by m has remainder n % m

gcd(n,m), gcd(list)

extended gcd g = sa + tb = gcd(a, b): g,s,t=xgcd(a,b)

lcm(n,m), lcm(list)

binomial coefficient \binom{m}{n} = binomial(m,n) digits in a given base: n.digits(base) number of digits: n.ndigits(base) (base is optional and defaults to 10) divides n | m: n.divides(m) if nk = m some k divisors – all d with d | n: n.divisors()

factorial – n! = n.factorial()

Prime Numbers

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …

factorization: factor(n)

primality testing: is prime(n), is pseudoprime(n)

prime power testing: is prime power(n) π(x) = #{p : p ≤ x is prime} = prime pi(x) set of prime numbers: Primes() {p : m ≤ p < n and p prime} =prime range(m,n)

prime powers: prime powers(m,n)
first n primes: primes first n(n)

next and previous primes: next prime(n),

  previous prime(n), next probable prime(n)
prime powers: next prime power(n),
  pevious prime power(n)

Lucas-Lehmer test for primality of 2^{p} − 1

  def is_prime_lucas_lehmer(p):
      s = Mod(4, 2^p - 1)
      for i in range(3, p+1): s = s^2 - 2
      return s == 0

Modular Arithmetic and Congruences

                                                                                                          k=12; m = matrix(ZZ, k, [(i*j)%k for i in [0..k-1] for j in [0..k-1]]); m.plot(cmap='gray')

Euler’s ϕ(n) function: euler phi(n)

                                                     Kronecker symbol (\frac{a}{b}) = kronecker symbol(a,b)
                                                     Quadratic residues: quadratic residues(n)

Quadratic non-residues: quadratic residues(n)

                                                     ring ℤ/nℤ = Zmod(n) = IntegerModRing(n)

a modulo n as element of ℤ/nℤ: Mod(a, n) primitive root modulo n = primitive root(n) inverse of n (mod m): n.inverse mod(m)

                                                     power a^{n} (mod m): power mod(a, n, m)

Chinese remainder theorem: x = crt(a,b,m,n) finds x with x ≡ a (mod m) and x ≡ b (mod n)

                                                     discrete log: log(Mod(6,7), Mod(3,7))
                                                     order of a (mod n) = Mod(a,n).multiplicative order()

square root of a (mod n) = Mod(a,n).sqrt()

Special Functions

                                                                                                          complex plot(zeta, (-30,5), (-8,8))

ζ(s) = ∏_{p} \frac{1}{1 − p^{−s}} = ∑ \frac{1}{n^{s}} = zeta(s)

Li(x) = ∫_{2}^{x} \frac{1}{log(t)}dt = Li(x)

Γ(s) = ∫_{0}^{∞} t^{s−1}e^{−t}dt = gamma(s)

Continued Fractions

                                                                                                                        continued fraction(pi)

π = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + ⋯}}}}

                                                                                                          continued fraction: c=continued fraction(x,bits)
                                                                                                          convergents: c.convergents()

convergent numerator p_{n} = c.pn(n) convergent denominator q_{n} = c.qn(n)

                                                                                                          value: c.value()

Elliptic Curves

                                                                                                                        EllipticCurve([0,0,1,-1,0]).plot(plot points=300,thickness=3)

                                                                                                            E = EllipticCurve([a_{1}, a_{2}, a_{3}, a_{4}, a_{6}])

y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}

conductor N of E =E.conductor()

discriminant Δ of E =E.discriminant()

                                                                                                          rank of E = E.rank()

free generators for E(ℚ) = E.gens()

                                                                                                          j-invariant = E.j invariant()

N_{p} = #{solutions to E modulo p} = E.Np(prime) a_{p} = p + 1 − N_{p} =E.ap(prime) L(E, s) = ∑ \frac{a_{n}}{n^{s}} = E.lseries()

                                                                                                          ord_{s=1} L(E, s) = E.analytic rank()

Elliptic Curves Modulo p

                                                                                                                        EllipticCurve(GF(997), [0,0,1,-1,0]).plot()

                                                                                                            E = EllipticCurve(GF(p), [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}])
                                                                                                          #E(𝔽_{p}) = E.cardinality()

generators for E(𝔽_{p}) = E.gens()

                                                                                                          E(𝔽_{p}) =E.points()