Number Theory
system:sage


<p>As you may have alreay guessed, much of elementary number theoretic aspects are implemented in SAGE. For example, the prime factorisation, primality test etc. Given a number N, SAGE can for example find the next probable prime.&nbsp;</p>

{{{id=1|
A = next_probable_prime(10^250)
///
}}}

{{{id=4|
A
///
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001227
}}}

{{{id=5|
A.is_prime()
///
True
}}}

{{{id=6|
timeit('A.is_prime()')
///
^CTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_9.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dGltZWl0KCdBLmlzX3ByaW1lKCknKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/xb/3311bnrd1lsfgk8pjr_v7d6r0000gn/T/tmpdW4r2V/___code___.py", line 2, in <module>
    exec compile(u"timeit('A.is_prime()')" + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "sage_timeit_class.pyx", line 117, in sage.misc.sage_timeit_class.SageTimeit.__call__ (build/cythonized/sage/misc/sage_timeit_class.c:1177)
  File "sage_timeit_class.pyx", line 81, in sage.misc.sage_timeit_class.SageTimeit.eval (build/cythonized/sage/misc/sage_timeit_class.c:965)
  File "/Users/apple/sage/local/lib/python2.7/site-packages/sage/misc/sage_timeit.py", line 243, in sage_timeit
    series = [s/number for s in timer.repeat(repeat, number)]
  File "/Users/apple/sage/local/lib/python/timeit.py", line 223, in repeat
    t = self.timeit(number)
  File "/Users/apple/sage/local/lib/python/timeit.py", line 195, in timeit
    timing = self.inner(it, self.timer)
  File "<magic-timeit>", line 6, in inner
  File "integer.pyx", line 4628, in sage.rings.integer.Integer.is_prime (build/cythonized/sage/rings/integer.c:28591)
  File "gen.pyx", line 1536, in sage.libs.pari.gen.gen.isprime (build/cythonized/sage/libs/pari/gen.c:10666)
  File "c_lib.pyx", line 73, in sage.ext.c_lib.sig_raise_exception (build/cythonized/sage/ext/c_lib.c:872)
KeyboardInterrupt
__SAGE__
}}}

{{{id=14|
N = 189768
N.factor()
///
2^3 * 3 * 7907
}}}

{{{id=15|
N.divisors()
///
[1, 2, 3, 4, 6, 8, 12, 24, 7907, 15814, 23721, 31628, 47442, 63256, 94884, 189768]
}}}

{{{id=16|
N.prime_divisors()
///
[2, 3, 7907]
}}}

{{{id=13|
euler_phi(488696228)
///
243849480
}}}

<p>Let us now do some Galois theory. Let us work out the Galois correspondence for a number field.&nbsp;</p>

{{{id=19|
K.<z> = NumberField(x^4+1)
G = K.galois_group(); G
///
Galois group of Number Field in z with defining polynomial x^4 + 1
}}}

{{{id=70|
G.gens()
///
[(1,2)(3,4), (1,4)(2,3)]
}}}

{{{id=71|
G.is_abelian()
///
True
}}}

{{{id=37|
H = pari('x^4+1').polgalois()
Gp = PariGroup(H, 4); Gp
///
PARI group [4, 1, 2, "E(4) = 2[x]2"] of degree 4
}}}

{{{id=20|
G.group_generators()
///
Family ((1,2)(3,4), (1,4)(2,3))
}}}

{{{id=21|
G.order()
///
4
}}}

{{{id=22|
sigma = G[1]; tau = G[2];
sigma,tau
///
((1,2)(3,4), (1,3)(2,4))
}}}

{{{id=23|
(sigma*tau)(1 + z + z^2 + z^3)
///
-z^3 + z^2 - z + 1
}}}

{{{id=24|
H = G.subgroup([sigma*tau]); H
///
Subgroup [(1,4)(2,3)] of Galois group of Number Field in z with defining polynomial x^4 + 1
}}}

{{{id=25|
H.order()
///
2
}}}

{{{id=26|
H.fixed_field()
///
(Number Field in z0 with defining polynomial x^2 + 4, Ring morphism:
  From: Number Field in z0 with defining polynomial x^2 + 4
  To:   Number Field in z with defining polynomial x^4 + 1
  Defn: z0 |--> 2*z^2)
}}}

<p>If the number field is not normal, we may compute the Galois closure:&nbsp;</p>

{{{id=28|
M.<a> = NumberField(x^3 - 2); M.galois_closure(names='b')
///
Number Field in b with defining polynomial x^6 + 108
}}}

<p>However, if I now ask for the Galois group, SAGE returns the Galois group of the Galois closure. (SAGE (the world in general?) does not know how to compute the Galois group of an extension that is not normal.)&nbsp;</p>

{{{id=30|
G = M.galois_group(names='b'); G.group_generators()
///
Family ((1,2,3)(4,5,6), (1,4)(2,6)(3,5))
}}}

{{{id=31|
G[1].as_hom()
///
Ring endomorphism of Number Field in b with defining polynomial x^6 + 108
  Defn: b |--> 1/12*b^4 - 1/2*b
}}}

{{{id=32|
K.<a, b> = NumberField([x^2 + 5, x^2 - 2])
L.<c, d> = NumberField([x^2 + 5, x^2 - 3])
composites = K.composite_fields(L, 'e', both_maps=true); composites
///
[[Number Field in e with defining polynomial x^8 - 24*x^6 + 464*x^4 + 3840*x^2 + 25600, Relative number field morphism:
  From: Number Field in a with defining polynomial x^2 + 5 over its base field
  To:   Number Field in e with defining polynomial x^8 - 24*x^6 + 464*x^4 + 3840*x^2 + 25600
  Defn: a |--> -9/66560*e^7 + 11/4160*e^5 - 241/4160*e^3 - 101/104*e
        b |--> -21/166400*e^7 + 73/20800*e^5 - 779/10400*e^3 + 7/260*e, Relative number field morphism:
  From: Number Field in c with defining polynomial x^2 + 5 over its base field
  To:   Number Field in e with defining polynomial x^8 - 24*x^6 + 464*x^4 + 3840*x^2 + 25600
  Defn: c |--> -9/66560*e^7 + 11/4160*e^5 - 241/4160*e^3 - 101/104*e
        d |--> -3/25600*e^7 + 7/1600*e^5 - 147/1600*e^3 + 1/40*e, None]]
}}}

{{{id=33|
KL = composites[0][0]
GKL = KL.galois_group(); GKL.group_generators()
///
Family ((1,2)(3,5)(4,6)(7,8), (1,5)(2,3)(4,8)(6,7), (1,7)(2,8)(3,4)(5,6))
}}}

{{{id=34|
GKL.order() == KL.degree()
///
True
}}}

{{{id=7|
x = polygen(QQ) 
K.<a> = NumberField(x^4 + 7*x^3 + 36)
///
}}}

{{{id=48|
K.degree()
///
4
}}}

{{{id=49|
K.signature()
///
(0, 2)
}}}

{{{id=72|
K
///
Number Field in z with defining polynomial x^4 + 1
}}}

{{{id=47|
rK = K.OK(); rK
///
Maximal Order in Number Field in z with defining polynomial x^4 + 1
}}}

{{{id=51|
rK.gens()
///
[1, z, z^2, z^3]
}}}

{{{id=40|
rK.discriminant()
///
256
}}}

{{{id=39|
UK = UnitGroup(K); UK
///
Unit group with structure C8 x Z of Number Field in z with defining polynomial x^4 + 1
}}}

{{{id=8|
UK.gens()
///
(u0, u1)
}}}

{{{id=9|
UK.gens_values()
///
[-z, z^3 + z^2 + z]
}}}

{{{id=10|
UK.fundamental_units()
///
[z^3 + z^2 + z]
}}}

{{{id=11|
UK.roots_of_unity()
///
[-z, z^2, -z^3, -1, z, -z^2, z^3, 1]
}}}

{{{id=12|
L.<b> = NumberField(x^4-8*x^2+36)
UL = UnitGroup(L); UL
///
Unit group with structure C4 x Z of Number Field in b with defining polynomial x^4 - 8*x^2 + 36
}}}

{{{id=35|
UL.roots_of_unity()
///
[-1/12*b^3 + 1/6*b, -1, 1/12*b^3 - 1/6*b, 1]
}}}

{{{id=45|
K.minkowski_bound()
///
24/pi^2
}}}

{{{id=46|
K.class_number()
///
1
}}}

{{{id=74|
K.class_group()
///
Class group of order 1 of Number Field in z with defining polynomial x^4 + 1
}}}

{{{id=52|
M.<d> = QuadraticField(-20072); M
///
Number Field in d with defining polynomial x^2 + 20072
}}}

{{{id=53|
M.class_number()
///
76
}}}

{{{id=54|
C = M.class_group(); C
///
Class group of order 76 with structure C38 x C2 of Number Field in d with defining polynomial x^2 + 20072
}}}

{{{id=55|
C.gens()
///
(Fractional ideal class (11, 1/2*d + 3), Fractional ideal class (13, 1/2*d))
}}}

{{{id=56|
#embeddings
E = M.complex_embeddings(); E #returns by default an embedding into Complex Lazy Field with 53 bits of precision
///
[
Ring morphism:
  From: Number Field in d with defining polynomial x^2 + 20072
  To:   Complex Field with 53 bits of precision
  Defn: d |--> -141.675685987399*I,
Ring morphism:
  From: Number Field in d with defining polynomial x^2 + 20072
  To:   Complex Field with 53 bits of precision
  Defn: d |--> 141.675685987399*I
]
}}}

{{{id=57|
phi = E[1]
///
}}}

{{{id=58|
phi(M(d+d^2))
///
-20072.0000000000 + 141.675685987399*I
}}}

{{{id=75|
#the computation is incomplete: this can be used to compute the regulator of K from first principles. Sage function does it too: 
K.regulator()
///
1.76274717403909
}}}

<p>Recall the notion of a different of a number field. For a lattice $L$ in a number field $K$, we may define its dual using the trace $\operatorname{Tr}_{K/\mathbf{Q}}$:&nbsp;</p>
<p>\[L^\vee = \{\alpha \in K: \operatorname{Tr}_{K/\mathbf{Q}}(\alpha L) \in \mathbf{Z}\}.\]</p>
<p>It is easy to verify that a fractional ideal $\mathfrak{a}$ gives a lattice in $K$; it turns out that $\mathfrak{a}^\vee$ is also a fractional ideal and satisfies:</p>
<p>\[\mathfrak{a}^\vee = \mathfrak{a}^{-1}\mathcal{O}_K^\vee.\]</p>
<p>The ideal $\mathcal{O}_K$ is a full sublattice of $K$ and $\mathcal{O}_K^\vee \subseteq \mathcal{O}_K$. Thus, the dual lattice gives us an interesting fractional ideal: the dual $\mathcal{O}_K^\vee$ is the largest fractional ideal whose all elements have integer trace. The inverse $(\mathcal{O}_K^\vee)^{-1}$, therefore an integral ideal, is called the different of the number field $K$.&nbsp;</p>

{{{id=59|
I = M.different(); I
///
Fractional ideal (d)
}}}

{{{id=61|
I.norm()
///
20072
}}}

{{{id=62|
#can factor principal ideals in a number field
M.factor(18)
///
(Fractional ideal (2, 1/2*d))^2 * (Fractional ideal (3, 1/2*d + 1))^2 * (Fractional ideal (3, 1/2*d + 2))^2
}}}

{{{id=63|
#you can factor elements of a number field
N.<w> = CyclotomicField(5); N
///
Cyclotomic Field of order 5 and degree 4
}}}

{{{id=64|
N(5).factor()
///
(w^3 - w - 1) * (w - 1)^4
}}}

{{{id=65|
N(20).factor()
///
(w^3 - w - 1) * 2^2 * (w - 1)^4
}}}

{{{id=67|
N(3).factor()
///
3
}}}

{{{id=68|

///
}}}