This notebook is licenced under CC BY-SA 4.0.

FriCAS Tutorial (Numbers)

Ralf Hemmecke <ralf@hemmecke.org>

Sources at Github.

In [1]:
)set message type off
)set output algebra off
setFormat!(FormatMathJax)$JFriCASSupport
)set message type on
In [2]:
)version

Value = "FriCAS a9422d32eb6f6b03d98ac6adfc9bf05ec0f5e8bd compiled at Sa 03 Apr 2021 00:29:13 CEST"

Finite rings

FriCAS allows to work in finite fields.

In [3]:
P := PrimeField 7;
a: P := 1
Out[3]:
Out[3]:
\[ 1 \]
In [4]:
(Integer has CharacteristicZero, P has CharacteristicNonZero)
Out[4]:
\[ \left[\texttt{true}, \texttt{true}\right] \]

Of course, all the field operations make sense.

In [5]:
a2 := a+a; a3 := a2 + a
Out[5]:
\[ 3 \]
In [6]:
a2 + a3 + 2
Out[6]:
\[ 0 \]
In [7]:
10*a2 - 5
Out[7]:
\[ 1 \]
In [8]:
1/a2
Out[8]:
\[ 4 \]

There is a simple way to work in arbitrary Galois fields.

In [11]:
F := FiniteField(2,3);
definingPolynomial()$F
basis()$F
Out[11]:
Out[11]:
\[ {\texttt{?}}^{3}+\texttt{?}+1 \]
Out[11]:
\[ \left[1, \%A, {\%A}^{2}\right] \]

A finite field is a cyclic group, so it has a primitive element.

In [12]:
f: F := primitiveElement()
Out[12]:
\[ \%A \]
In [13]:
[f^i for i in 0..7]
Out[13]:
\[ \left[1, \%A, {\%A}^{2}, \%A+1, {\%A}^{2}+\%A, {\%A}^{2}+\%A+1, {\%A}^{2}+1, 1\right] \]

All the field axioms hold.

In [14]:
1/f
Out[14]:
\[ {\%A}^{2}+1 \]

Also finding solutions of polynomials over finite fields works.

In [15]:
solve(f*y^2 + 1$F, y)
Out[15]:
\[ \left[y=\%A+1\right] \]

Similarly, one can construct and work with matrices over finite fields.

In [17]:
M := SquareMatrix(2, F);
m: M := matrix [[1, f],[1+f, f]]
Out[17]:
Out[17]:
\[ \begin{bmatrix}1&\%A\\\%A+1&\%A\end{bmatrix} \]
In [18]:
m * transpose(m) + m
Out[18]:
\[ \begin{bmatrix}{\%A}^{2}&{\%A}^{2}+1\\{\%A}^{2}&\%A+1\end{bmatrix} \]
In [19]:
(M has Field, M has Ring, M has CommutativeRing)
Out[19]:
\[ \left[\texttt{false}, \texttt{true}, \texttt{false}\right] \]

We can have finite rings with zero divisors.

In [22]:
W := IntegerMod(6);
w2: W := 2
w3: W := 3
Out[22]:
Out[22]:
\[ 2 \]
Out[22]:
\[ 3 \]
In [23]:
w2*w3
Out[23]:
\[ 0 \]
In [24]:
w2^2+w3
Out[24]:
\[ 1 \]
In [25]:
(W has Ring, W has noZeroDivisors)
Out[25]:
\[ \left[\texttt{true}, \texttt{false}\right] \]

The "false" that is returned by the following operation is to be interpreted as: "It is not know whether IntegerMod(7) has no zero divisors".

In [26]:
IntegerMod(7) has noZeroDivisors
Out[26]:
\[ \texttt{false} \]

By general principle, FriCAS can construct power series over finite fields.

Integers localized at a prime

Sometimes it might be useful to work with rational numbers with the condition that no denominator is divisible by a certain prime. Such structures are implemented in FriCAS by the domain IntegerLocalizedAtPrime(p). This domain is a ring.

In [27]:
Z3 ==> IntegerLocalizedAtPrime 3
Out[27]:

Elements are created by retracting rational numbers.

In [29]:
x := retract(7/4)$Z3
y := retract(1/2)$Z3
Out[29]:
\[ \frac{7}{4} \]
Out[29]:
\[ \frac{1}{2} \]

Of course, it must be an error, if you try to consider a rational number that has a denominator that is divisible by the prime as an element of the localized ring.

In [30]:
retractIfCan(2/27)$Z3
Out[30]:
\[ \texttt{"failed"} \]
Union("failed",...)
In [25]:
retract(2/27)$Z3

   >> Error detected within library code:
   denominator contains power of p

The sum $x+y$ gives $\frac{9}{4}=3^2\cdot\frac{1}{4}$.

In [31]:
z := x+y
Out[31]:
\[ {3}^{2}\, \frac{1}{4} \]

Clearly, Z3 is not a field, but a commutative ring without zero divisors.

In [32]:
(Z3 has Field, Z3 has CommutativeRing, Z3 has noZeroDivisors)
Out[32]:
\[ \left[\texttt{false}, \texttt{true}, \texttt{true}\right] \]

Internally, the number is stored as a pair consisting of a power of the prime together with a unit of the ring.

In [34]:
exponent z
unit z
Out[34]:
\[ 2 \]
Out[34]:
\[ \frac{1}{4} \]

Since Z3 is not a field, ordinary division cannot be done in Z3, so FriCAS extends the domain by applying the Fraction constructor (see result type).

In [36]:
x/y
y/z
Out[36]:
\[ \frac{7}{2} \]
Out[36]:
\[ \frac{2}{{3}^{2}} \]

Z3 is even a Euclidean domain, so the Euclidean algorithm can be applied.

In [37]:
Z3 has EuclideanDomain
Out[37]:
\[ \texttt{true} \]
In [38]:
euclideanSize z
Out[38]:
\[ 2 \]
In [39]:
t := retract(27/5)$Z3
Out[39]:
\[ {3}^{3}\, \frac{1}{5} \]
In [40]:
gcd(x,y), gcd(t,z)
Out[40]:
\[ \left[1, {3}^{2}\right] \]

In a Euclidean domain, we can do division with remainder.

In [43]:
divide(x,y)
divide(y,z)
divide(t,z)
Out[43]:
\[ \left[quotient=\frac{7}{2}, remainder=0\right] \]
Out[43]:
\[ \left[quotient=0, remainder=\frac{1}{2}\right] \]
Out[43]:
\[ \left[quotient=3\, \frac{4}{5}, remainder=0\right] \]

If we know in advance that the division has a zero remainder, we can use the exquo function and retract the result into an element of Z3.

In [44]:
1 exquo x
Out[44]:
\[ \frac{4}{7} \]
In [45]:
(t exquo z)::Z3
Out[45]:
\[ 3\, \frac{4}{5} \]
In [46]:
unitNormal z
Out[46]:
\[ \left[unit=\frac{1}{4}, canonical={3}^{2}, associate=4\right] \]