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]$