Number theory

Modulo calculations consider the remainder of a division. One simple example is the clock. 17 o'clock is equal to 5 o'clock.

In sagemath, modulo computation is available via the % operator:

In [1]:
17 % 12
Out[1]:
5

Another way is the use of the mod function:

In [2]:
mod(21, 12)
Out[2]:
9

It is also possible to create an object which contains all remainders of divisions by 12:

In [3]:
clock = Integers(12)

Using the clock instance, we can instantiate member 21. Its representation reveals number 21 reduced modulo 12:

In [4]:
print(clock(21))

9

Informal definition of finite fields

A field is a set where you can add, substract, multiply and divide the elements and the solution is also in this set.

Such a finite field can be created using the following commands. Be aware that the order has to be a prime power.

In [5]:
F.<a> = GF(5)
F.<a> = FiniteField(9)
show(F)

If we want to see if a number is prime, we can use Primes:

In [6]:
13 in Primes()
Out[6]:
True
In [7]:
2019 in Primes()
Out[7]:
False

2019 is not a prime number? Then it must have some interesting prime factorisation:

In [8]:
2019.factor()
Out[8]:
3 * 673

Which elements are in F?

In [9]:
print(list(F))

[0, a, a + 1, 2*a + 1, 2, 2*a, 2*a + 2, a + 2, 1]

Back to the clock

What are the elements in our clock?

In [10]:
print(list(clock))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Sagemath can even display the operation table. But some import is needed:

In [11]:
from sage.matrix.operation_table import OperationTable
OperationTable(clock, operation=operator.add)
Out[11]:
+  a b c d e f g h i j k l
 +------------------------
a| a b c d e f g h i j k l
b| b c d e f g h i j k l a
c| c d e f g h i j k l a b
d| d e f g h i j k l a b c
e| e f g h i j k l a b c d
f| f g h i j k l a b c d e
g| g h i j k l a b c d e f
h| h i j k l a b c d e f g
i| i j k l a b c d e f g h
j| j k l a b c d e f g h i
k| k l a b c d e f g h i j
l| l a b c d e f g h i j k

For better readability we can use digits instead of letters:

In [12]:
OperationTable(clock, operation=operator.add, names='digits')
Out[12]:
 +  00 01 02 03 04 05 06 07 08 09 10 11
  +------------------------------------
00| 00 01 02 03 04 05 06 07 08 09 10 11
01| 01 02 03 04 05 06 07 08 09 10 11 00
02| 02 03 04 05 06 07 08 09 10 11 00 01
03| 03 04 05 06 07 08 09 10 11 00 01 02
04| 04 05 06 07 08 09 10 11 00 01 02 03
05| 05 06 07 08 09 10 11 00 01 02 03 04
06| 06 07 08 09 10 11 00 01 02 03 04 05
07| 07 08 09 10 11 00 01 02 03 04 05 06
08| 08 09 10 11 00 01 02 03 04 05 06 07
09| 09 10 11 00 01 02 03 04 05 06 07 08
10| 10 11 00 01 02 03 04 05 06 07 08 09
11| 11 00 01 02 03 04 05 06 07 08 09 10

In our case, it's the best to use the original elements of the clock:

In [13]:
OperationTable(clock, operation=operator.add, names='elements')
Out[13]:
 +   0  1  2  3  4  5  6  7  8  9 10 11
  +------------------------------------
 0|  0  1  2  3  4  5  6  7  8  9 10 11
 1|  1  2  3  4  5  6  7  8  9 10 11  0
 2|  2  3  4  5  6  7  8  9 10 11  0  1
 3|  3  4  5  6  7  8  9 10 11  0  1  2
 4|  4  5  6  7  8  9 10 11  0  1  2  3
 5|  5  6  7  8  9 10 11  0  1  2  3  4
 6|  6  7  8  9 10 11  0  1  2  3  4  5
 7|  7  8  9 10 11  0  1  2  3  4  5  6
 8|  8  9 10 11  0  1  2  3  4  5  6  7
 9|  9 10 11  0  1  2  3  4  5  6  7  8
10| 10 11  0  1  2  3  4  5  6  7  8  9
11| 11  0  1  2  3  4  5  6  7  8  9 10

OEIS (Online Database of Integer Sequences) [oeis.org]

Take a list and search for a sequence containing these numbers

In [14]:
search = oeis([1, 1, 2, 3], max_results=4)
print(search)

0: A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
1: A000041: a(n) is the number of partitions of n (the partition numbers).
2: A112798: Table where n-th row is factorization of n, with each prime p_i replaced by i.
3: A001405: a(n) = binomial(n, floor(n/2)).

Take the Fibonacci numbers and calculate the first 15 terms

In [15]:
c = search[0]
c.first_terms(15)
Out[15]:
(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377)

We can also search by the name of a sequence

In [16]:
search = oeis.find_by_description('catalan')
print(search)

0: A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers.
1: A014137: Partial sums of Catalan numbers (A000108).
2: A014138: Partial sums of (Catalan numbers starting 1, 2, 5, ...).
In [17]:
search[0].first_terms(4)
Out[17]:
(1, 1, 2, 5)