Sage Quick Reference:
Elementary Number Theory
William Stein
Sage Version 3.4
http://wiki.sagemath.org/quickref
GNU Free Document License, extend for your own use

Modular Arithmetic and Congruences

Continued Fractions

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’)continued_fraction(pi)

0
1
2
3
4
5
67
8
91011

Everywhere m, n, a, b, etc. are elements of ZZ
ZZ = Z = 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 mn = 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 kdivisors – 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 2p − 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 == 00 1 2 3 4 5 6 7 8 9 10 110
12345678910
110 1 2 3 4 5 6 7 8 9 10 11

1π =3+

1

7+

1

15 +1+

1
292 + · · ·continued fraction: c=continued fraction(x, bits)
convergents: c.convergents()
convergent numerator pn = c.pn(n)convergent denominator qn = c.qn(n)value: c.value()

Euler’s φ(n) function: euler phi(n)Kronecker symbol ab = kronecker symbol(a,b)
Quadratic residues: quadratic residues(n)Quadratic non-residues: quadratic residues(n)ring Z/nZ = Zmod(n) = IntegerModRing(n)Elliptic Curvesa modulo n as element of Z/nZ: Mod(a, n)EllipticCurve([0,0,1,-1,0]).plot(plot_points=300,thickness=3)
primitive root modulo n = primitive root(n)inverse of n (mod m): n.inverse mod(m)power an (mod m): power mod(a, n, m)
Chinese remainder theorem: x = crt(a,b,m,n)
E = EllipticCurve([a1 , a2 , a3 , a4 , a6 ])finds x with x ≡ a (mod m) and x ≡ b (mod n)
discrete log: log(Mod(6,7), Mod(3,7))
y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6
order of a (mod n) =Mod(a,n).multiplicative order()conductor N of E =E.conductor()square root of a (mod n) =Mod(a,n).sqrt()
discriminant ∆ of E =E.discriminant()
rank of E = E.rank()Special Functions
free generators for E(Q) = E.gens()
complex_plot(zeta, (-30,5), (-8,8))
j-invariant = E.j invariant()
Np = #{solutions to E modulo p} = E.Np(prime)
86ap = p + 1 − Np =E.ap(prime)
4P an
2L(E, s) =
-15-5
5-30
-25
-20-10ns = E.lseries()-2-4
ords=1 L(E, s) = E.analytic rank()
1.5
10.5

-1-0.50.5-0.5-1-1.5-2

1

1.5-6-8

Elliptic Curves Modulo p
1−s =pns = zeta(s)R x 1−p1Li(x) = 2 log(t) dt = Li(x)R∞Γ(s) = 0 ts−1 e−t dt = gamma(s)ζ(s) =QP 1

EllipticCurve(GF(997), [0,0,1,-1,0]).plot()
1000
750
500
250
250500750

1000

E = EllipticCurve(GF(p), [a1 , a2 , a3 , a4 , a6 ])#E(Fp ) = E.cardinality()
generators for E(Fp ) = E.gens()
E(Fp ) =E.points()