0
$\begingroup$

I came across this quote while studying Linear systems over $\mathbb{Z_p}$ where the author of the book I am reading casually states

When p is a prime number, ℤp behaves a lot like ℝ in particular, we can add, subtract, multiply, and divide (by nonzero numbers)

I am very confused through this statement, why would that be the case, I've tried myself and I can't find a difference between behaviour in $\mathbb{Z_3}$ and $\mathbb{Z_4}$. Do you know what he is referring to?

Thank you.

$\endgroup$
3
  • 1
    $\begingroup$ in $\mathbb Z_4$ you cannot divide by 2. In fact $6\equiv 2$, but if you divide you get $3\not\equiv 1$ $\endgroup$
    – Exodd
    Dec 18, 2020 at 22:50
  • 1
    $\begingroup$ They mean $\mathbb{Z}_P$ is a field when $P$ is prime. Not sure if the similarities go much further than that. $\endgroup$
    – JKEG
    Dec 18, 2020 at 22:51
  • 2
    $\begingroup$ I'd just like to point out that while the notation $\mathbb Z_p$ for the finite field with $p$ elements i.e. the quotient ring $\mathbb Z/(p)$ is not uncommon, most algebraists I know prefer $\mathbb F_p$. Part of the reason is that $\mathbb Z_p$ is the standard notation for the ring of $p$-adic integers, which is a (not entirely unrelated but) very different algebraic structure. Just saying that if everyone here wrote $\mathbb Z/n$ instead of $\mathbb Z_n$, I would appreciate it a lot. $\endgroup$ Dec 19, 2020 at 5:42

3 Answers 3

4
$\begingroup$

The key difference is that $\mathbb{Z}_p$ forms what's called a field, like $\mathbb{R}$, but unlike e.g. $\mathbb{Z}_4$. For instance, we can't define $1/2$ in $\mathbb{Z}_4$ because there's no number $b$ such that $2\cdot b=1$, but in $\mathbb{Z}_5$, say, we have $1/2=3$ since $3\cdot 2\equiv 1\pmod 5$. The essential property is that there are no zero divisors in $\mathbb{Z}_p$, so division is well-defined for all (non-zero) members of it.

Incidentally, there are other finite fields, including one with four elements; more specifically, for any prime $p$ and any $n$ there's a field $F_{p^n}$ with $p^n$ elements. But they're a bit more complicated to think about, as addition and multiplication in the field don't quite map to addition and multiplication as integers. For instance, in $F_4$ we can write the elements as $0$, $1$, $\alpha$, and $1+\alpha$; we have $a+a=0$ for all $a\in F_4$ so each element is its own additive inverse, and $\alpha\cdot(1+\alpha)=1$, so these two elements are multiplicative inverses of each other. (See if you can figure out what $\alpha^2$ and $(1+\alpha)^2$ are, knowing these facts; there are multiple ways of doing this). The fields with $2^n$ elements see quite a bit of use in the mathematics of encryption, since it's handy for calculation purposes to be able to do all the relevant arithmetic operations on $n$-bit 'numbers'.

$\endgroup$
1
  • 1
    $\begingroup$ @Sdavid552 You're right on all fronts - but you can write those even more explicitly. For instance, $(1+\alpha)^2 = (1+\alpha)\cdot(1+\alpha) = (1+\alpha)+\alpha\cdot(1+\alpha)=\ldots$? $\endgroup$ Dec 18, 2020 at 23:41
1
$\begingroup$

The author of your book is probably refering to the fact that both $\mathbb{Z_p}$ and $\mathbb{R}$ are fields. The main difference between $\mathbb{Z_3}$ and $\mathbb{Z_4}$ is that the former is a field and the latter is only a ring, which is a structure with less requisites (all fields are rings but not all rings are fields). Observe that 2 doesn't have an inverse in $\mathbb{Z_4}$ because $2\cdot 0=0$, $\space$ $2\cdot 1=2$, $\space$ $2\cdot 2=4=0$ and $2\cdot 3=6=2$. We cannot find an element of $\mathbb{Z_4}$ that multiplied by 2 gives the identity 1. Another important thing is that we have zero divisors, that is, a non zero element such that multiplied by another non zero element gives 0. In this case 2 is a zero divisor since $2\cdot 2=0$. $\mathbb{Z_n}$ is a field only when n is prime.

$\endgroup$
2
  • $\begingroup$ So, would you only consider it a field if all of its components have an inverse. As in $\mathbb{Z_4}$, $1⋅1=1, 1/1 = 1$. Nevertheless, thank you for the great response. $\endgroup$
    – user854748
    Dec 18, 2020 at 23:22
  • 1
    $\begingroup$ Yes. If a set $A$ is a field all non zero elements of $A$ have an inverse. If $0$ has an inverse the distributive property does not verify. This only happens in one case: the zero ring or trivial ring. $\endgroup$
    – DaifM
    Dec 18, 2020 at 23:33
0
$\begingroup$

The author most likely refers to the fact that $\mathbb{Z}_p$ is a field if and only if $p$ is a prime number. A field is an ordered triple $(S,+,\cdot)$ where $S$ is a set and $+$, $\cdot$ are binary operations defined on $S$ which satisfy the field axioms. (Note that the "addition" and "multiplication" operations here are not necessarily the usual addition/multiplication operations you had previously encountered on real numbers).

These axioms are chosen in a way to allow us to meaningfully define addition, subtraction, multiplication and division in a similar way that we would define them on $\mathbb{R}$:

  • Axiom 1 Addition is commutative: $\forall a,b \in S$, $a+b=b+a$

  • Axiom 2 Addition is associative: $\forall a,b,c \in S$, $a+(b+c)=(a+b)+c$

  • Axiom 3 Addition has an identity element: $\exists 0_S \in S$ $\forall a \in S$, $a+0_S=a$ (This is referred to as the "Zero element" of the field, but keep in mind that this is not necessarily the number $0 \in R$)

  • Axiom 4 Additive inverses exist: $\forall a \in S$ $\exists -a \in S$, $a + (-a) = 0_S$ (Note that $-a$ is only a symbol here, the property of "Minus $a$" being the additive inverse of $a$ is only meaningful when we have this axiom. In other words, we state that there exists a "Minus $a$" for every $a$.)

  • Axiom 5 Multiplication is commutative: $\forall a,b \in S$, $a \cdot b = b \cdot a$

  • Axiom 6 Multiplication is associative: $\forall a,b,c\in S$, $a \cdot (b \cdot c) = (a \cdot b) \cdot c$

  • Axiom 7 Multiplication has an identity element: $\exists 1_S \in S$ $\forall a \in S$, $a \cdot 1_S = a$ (This is referred to as the "One element" of the field, but keep in mind that this is not necessarily the number $1 \in R$)

  • Axiom 8 Multiplicative inverses exist: $\forall a \in S \backslash \{0_S\}$ $\exists a^{-1} \in S$, $a \cdot a^{-1} = 1_S$ (Similar to Axiom 4, we state that there exists a "reciprocal of $a$" for every $a$, but this time except $0_S$.)

  • Axiom 9 Multiplication is distributive over addition: $\forall a,b,c\in S$, $a \cdot (b+c) = a \cdot b + a \cdot c$

All of these might seem obvious in a sense, but that's only because you're used to the algebraic manipulation in real numbers that involves these properties of real numbers. Indeed, all of these axioms hold for the set of real numbers and usual addition/multiplication. Turns out there are many other structures that satisfy all of these axioms, and thus behave like real numbers. (You might want to pick up an abstract algebra textbook for interesting examples).

As to why $\mathbb{Z}_n$ only behaves like $\mathbb{R}$ when $n$ is a prime, consider the following example:

Assume that you don't know what rational numbers are, and the only number system that you're familiar with is the set of integers $\mathbb{Z}$ (With the usual addition and multiplication, of course). Now, does the expression $5^{-1}$ make sense in this context?

The answer is obviously no. $5^{-1}$ refers to the "reciprocal of 5", or rather the multiplicative inverse of 5, which does not exist in $\mathbb{Z}$. We can safely say that $(\mathbb{Z},+,\cdot)$ does not satisfy axiom 8, and thus is not a field.

In a very similar way, $\mathbb{Z}_n$ satisfies axiom 8 only when $n$ is a prime. When $n$ is composite, there exist (possibly multiple) elements $a\in \mathbb{Z}_n$ with no multiplicative inverse. (Again, you might want to take a look at an introductory abstract algebra textbook for a proof of this)

Sorry for the wall of text, I hope I could make everything clear.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy