Modular Arithmetic, Complex Numbers, Equations and Varieties

4. Modular Arithmetic


Modular arithmetic facilitates using finite number systems to study the integers, which provides advantages in the development of algebraic number theory (ANT), particularly in regard to characterizing solutions to equations. For an initial example, it will be shown that the equation {x^2 + y^2=a}, with {x}, {y}, and {a} integers, has no solutions if {4 | (a-3)}, and a new symbolic way of expressing this condition on {a} will be developed.

In modular arithmetic, which resembles integer arithmetic, a fixed subset of the integers is selected, say the {p} integers from {0} to {p-1}. Then any other integer is determined to be equivalent to one of these first {p} integers if it differs by some multiple of {p}, called the modulus. In other words, equivalent integers give the same remainder when dividing by {p}. Thus modular arithmetic is sometimes called remainder arithmetic. Arithmetic modulo {p} divides the integers into {p} equivalence classes.

The first {p} integers beginning at {0}, called here {\mathbb{F}_p}, each appear in a different equivalence class. {\mathbb{F}_p} becomes a finite number system under arithmetic modulo {p}. Modular equivalence can be expressed symbolically using a notation attributed to Gauss. Given integers {a}, {b}, {m}, write the congruence (equivalence) relation of {a} and {b} modulo {m} as {a \equiv b \pmod m}, read {a} is congruent to {b} modulo {m}, where {m} is said to be the modulus of the congruence. It means that when dividing {a} and {b} by {m}, one gets the same remainder; or alternatively {a-b} is a multiple of {m}, written {m|(a-b)}.

An arithmetic progression provides a basis for understanding equivalence of modular numbers. Letting the modulus {p=7}, consider the arithmetic progression {5,12,19,26,33,40,\ldots} , where each number in sequence is obtained by adding {7} to the prior number. In context, this series is called a congruence class modulo {7}, specifying all the integers in {\mathbb{Z}} equivalent to {5} in {\mathbb{F}_7}, where equivalent means they all give the remainder {5} when divided by the modulus {7}. The series contains the solutions (all the integers {x}) satisfying the equation {x-5=7n}, {n=0,1,2,,}. Written as above, {x \equiv 5 \pmod 7} represents all the equivalent integers {x} that are congruent to {5 \pmod 7}.

Modular arithmetic has been called ‘clock’ arithmetic because hours repeat modulo {12} on a clock face (replacing {12} by {0} to be consistent with the above). For example, if it is noon and one asks what time it will be { 3 3 } hours from now, the answer is {9}PM, or {33 \equiv 9 \pmod{12}}. (Aside: It has been suggested that the congruence relation be more intuitively expressed, perhaps e.g. {33 =_{12} 9}. This captures the notion of a binary relation similar to the equals relation: 33 equals 9 except for some multiple of 12. But such notation has not been adopted.)

The finiteness of modular arithmetic facilitates formulating algebraic expressions that apply to all of {\mathbb{Z}}. For example, the consecutive powers of a prime {p} in modulo {p} arithmetic must eventually repeat (reach equivalence with a prior power). Using this, Fermat showed, for prime number p, {x^{p-1}\equiv 1 \pmod p} for all integers {x\ne np}. The main interest in modular arithmetic here remains its utility in determining characteristics of the solutions of sets of equations.

What are the rules of modular arithmetic? Just as things equal to same thing are equal to each other (Euclid), if {a \equiv b \pmod n} and {b \equiv c \pmod n} then {a \equiv c \pmod n}. This is called the transitive property of equivalences. The symmetric and reflexive properties also obtain: {a \equiv b \pmod n} implies {b \equiv a \pmod n}; {a \equiv a \pmod n}. Modular arithmetic possesses the usual algebraic properties of numeric equivalences. If {a \equiv b \pmod n} and {c \equiv d \pmod n} then {ac \equiv bd \pmod n} and {a+c \equiv b+d \pmod n}. {ac \equiv bc \pmod n} implies {a \equiv b \pmod n} only when {c \neq 0} and {n} and {c} have no common divisors except {1} (they are relatively prime, aka coprime).

The rules of modular arithmetic become more regular if the modulus is a prime, as seen above with regard to the cancellation rule. Reviewing, a prime number is an integer greater than 1 that is divisible by no integers other than 1 and itself. All non-prime integers are called composite numbers, and the Fundamental Theorem of Arithmetic states that each composite number has a unique representation, independent of order, as a product of prime numbers. From now on here, modular arithmetic is modulo {p} where {p} is a prime number.

{\mathbb{F}_p} is a number system with characteristic {p}, where {p} is the cardinality of {\mathbb{F}_p}. {\mathbb{F}_p} can be considered as a group under addition, where the identity element is {0} and the additive inverse of a number {a} is the number {p-a}. {\mathbb{F}^ \times_p}=\mathbb{F}_p \setminus 0 = \{1, 2, 3, \ldots, p-1\} is a group under multiplication, where the identity element is {1} and the multiplicative inverse for an element {x} is a solution to the equation {xx^{\prime} \equiv 1 \pmod p}. Both {\mathbb{F}_p} and {\mathbb{F}^ \times_p} are cyclic groups.

A field is a number system where division by a non-zero element is defined. The integers have no multiplicative inverse defined. They are not a field, but rather an integral domain. Division is defined for {\mathbb{F}_p}, however. Let {x} be an element of the field, {x \neq 0}. Then as for the group {\mathbb{F}^ \times_p} above, each element {x} has an inverse {x^{\prime}} that is a solution to the equation {xx^{\prime} \equiv 1 \pmod p}. This defines {x^{\prime}} as the inverse of {x}, so division can be defined as multiplication by {x^{\prime}}. By our definition, {\mathbb{F}_p} is thus a field. For a finite field with characteristic {p}, the sum formed by adding any field element to itself {p} times is {0}. (Aside: There are finite fields whose cardinality is a composite number, and this number is always the power of a prime, but that discussion is not germane here.)

Returning to the final example of the Motivation paragraph, the utility of modular arithmetic can be demonstrated in classifying solutions to equations, e.g. the solutions to the equation {x^2+y^2= a}. Assuming there are some solutions, can one determine conditions on {a} for which solutions do not exist?  Recalling that equal values are congruent under any modulus, consider the modular version of the equation, {x^2+y^2\equiv a \pmod 4}. Because {x^2} has the interesting property that it is either {0} or {1\ (mod\ 4)}, and similarly for {y^2}, then {x^2+y^2} is either {0}, {1}, or {2\ (mod\ 4)}. This implies there can be no solutions if {a \equiv 3 \pmod 4}.

5. Complex Numbers

The complex numbers arise in solutions of polynomial equations. A polynomial {p(x)} in one variable of degree {n} looks like this:

\displaystyle a_nx^n + a^{n-1}x^{n-1}+ \ldots + a_1x+a_0

where n is an integer, both the coefficients of the variable terms {x^j} and the values assumed by the variable are elements of some number systems, and addition, subtraction, and multiplication of terms follows the algebraic rules of those number system(s). A polynomial equation is formed by equating two polynomials. In our usual case, the second polynomial is just {0}, {p(x)=0}. Such polynomial equations are also called algebraic equations. The equation {x^2-2=0} is a polynomial equation of degree 2, a quadratic equation.

The need for complex numbers arose from the same type of practical (extrinsic) mathematical considerations that produced the other number systems we use. Once the need was established, the modern mathematical world needed a systematic (intrinsic) structure to incorporate the complex numbers into the theory of number systems.

Extrinsic Motivation

To appreciate the complex numbers, it helps to know their context and history. Here’s a fly-by of how number systems have evolved to solve practical problems. The problem of counting required the natural numbers {\mathbb{N}}, whose use is older than history and is in a limited sense pre-wired in brains. The problem of measuring can’t be solved by the whole numbers, because a measure may lay between two whole numbers. The ancient Egyptians were using fractions of the form of {1/n} to subdivide the space between two whole numbers, enabling measurement to any desired accuracy as a sum of fractions. The classical Greek mathematicians generalized fractions to the concept of ratios {m/n} (the root of the word rational). They also developed abstract mathematical reasoning and thereby came to a proof that the measure of the hypotenuse of a square {1} unit on a side is not commensurate with any ratio. Thus the irrational numbers were conceived to represent solutions to such equations as {x^2=2}. Over the next millennium or so, mathematical progress occurred variously around the globe, including China, India, and Arabia. Perhaps the problem of bookkeeping (the need to represent monies owed) caused the gradual recognition of negative quantities as valid numbers. Finally, zero was promoted from a cipher or place marker to the status of a number and our current number systems for solving various problems were nearly complete. But recognition and acceptance in Europe was slow and not until the 18th century were negative numbers fully accepted as meaningful. By the 16th century, progress was being made in classifying solutions to general polynomial equations. In addition to the quadratic, the cubic and quartic polynomials of degrees {3} and {4} were solved algebraically. Solutions that were not positive real numbers were typically ignored as meaningless. The real numbers sufficed in practice. In quadratic equations, roots that involved the ‘imaginary’ quantity called {i},where {i^2=-1}, were just discarded. But during the search for a general algebraic solution to the cubic equation, it became mathematically necessary to deal with these imaginary quantities, because real roots of these equations could not be computed without them.

Intrinsic Motivation

The historical rationale above documents the practical evolution of our number systems. There is an even more powerful evolutionary motivation, the intrinsic mathematical motivation toward generalization. By the mid 19th century, the generalized concept of integral domain and number field were established and our number systems were categorized, generalized, and formalized. {\mathbb{Z}} is called an integral domain. {\mathbb{Q}} extends {\mathbb{Z}} by adding inverse elements and is the smallest field with characteristic {0} (meaning there is no element which added to itself a finite number of times gives {0}). {\mathbb{R}} extends {\mathbb{Q}} by adding the irrational numbers. Geometrically, {\mathbb{R}} represents all the points on the {x}-axis of the Cartesian plane, which means it is an ordered field in the sense of a ‘greater than’ relationship. {\mathbb{C}} was established in the first 30 years of the 19th century as an extension of {\mathbb{R}} to include {i}. This extension consists of all pairs of real numbers {\mathbb{R} \times \mathbb{R}}. Geometrically, {\mathbb{C}} represents the points in the Cartesian plane, and so possesses no intrinsic ordering. {\mathbb{R}} is not closed, meaning solutions to polynomial equations with real coefficients are not always real numbers, as evidenced by {x^2+1=0}. {\mathbb{C}} is closed via the Fundamental Theorem of Algebra: {\mathbb{C}} is sufficient for representing solutions of all equations involving a polynomial of any degree in one variable with coefficients in {\mathbb{C}}. The nesting: {\mathbb{N}\subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}} shows that {\mathbb{C}} is the general number system that includes all the polynomial solutions, making {\mathbb{C}} the ‘end of the road’ number system for the purpose of characterizing solution sets to systems of algebraic equations. Actually, a subfield of {\mathbb{C}} will do, as will be seen.

The complex numbers {\mathbb{C}}, considered as a set, are {\mathbb{R}^2}. Thus complex numbers are simply pairs of real numbers, as is expected from their geometric visualization as points in the Cartesian plane. Writing a complex number as a pair {(a, b)}, algebraic operations are provided to obtain desirable field-like properties, and specifically to cause {i^2=-1}:

\displaystyle (a_1,b_1)+(a_2,b_2)=(a_1+a_2,b_1+b_2)

\displaystyle (a_1,b_1)(a_2,b_2)=(a_1a_2-b_1b_2,a_1b_2+a_2b_1)

Identifying {(a,0)} with the real number {a} enables {\mathbb{R} \subset \mathbb{C}}. Writing the symbol {i} as {(0,1)} satisfies {i^2=(-1,0)=-1}. The additive identity is {0} and the multiplicative identity is {1}. These conventions together with the rules for addition and multiplication above enables writing an equivalent vector representation

\displaystyle a+bi=(a,0)+(b,0)(0,1)=(a,b)

where {a} is called the real part and {bi} is called the imaginary part. This notation is useful for developing the algebraic operations on {\mathbb{C}}. In the Cartesian plane geometry, multiplying numbers in the plane by {+i} rotates the plane about the origin 90° CCW, and multiplication by {-i} rotates it 90° CW.

Since {\mathbb{C}} is a field, there must be some inverses. Let {z} be a complex number, {z=a+bi\neq0}. Look for another complex number, say {z^{\prime}} such that {zz^{\prime}=1}. It becomes useful here to define the complex conjugate of {z}, {\bar{z}=a-bi}. The associated mapping {z\rightarrow\bar{z}} is an automorphism (isomorphism with itself) on {\mathbb{C}} that effects a reflection of the complex plane about the {x}-axis, leaving only {\mathbb{R}} invariant. Note also that {z\bar{z}=a^2+b^2\neq0}, a real number whose square root is called the modulus of {z}, written {|z|=\sqrt{a^2+b^2}}. Geometrically, {|z|} is the distance in the Cartesian plane from point {(a,b)} to the origin. Eureka, the prior equation looks a lot like {zz^{\prime}=1}, by just letting {z^{\prime}=\bar{z}/|z|^2}. Thus the inverse of any element {z} is {\bar{z}/|z|^2}.

{\mathbb{C}} is for immediate purposes the end of the number system road, but {\mathbb{C}} is big. Not all of {\mathbb{C}} is needed to get to the final destination. Rather, a sub-field of {\mathbb{C}} is needed, called the algebraic numbers, {\overline{\mathbb{Q}}}. How big is {\overline{\mathbb{Q}}}? It is a countable set, meaning there is an isomorphism from {\overline{\mathbb{Q}}} to {\mathbb{Z}}. Now that’s small, as infinities go. {\overline{\mathbb{Q}}} is characterized as the set of solutions to non-zero polynomial equations with integer coefficients.

5.1. Supplement: Limit Process and the Number Continuum

Of all the subset relations between number systems above, by far the deepest is the transition from {\mathbb{Q}} to {\mathbb{R}}. It is deep because it spans the intuitive divide between a discrete (countable) set and the mathematical continuum, an example of an uncountable set. The following draws back the veil a little on these deeper issues.

The scholars of the classic Greek period discovered that {\mathbb{Q}} is missing points needed to measure some quantities. In particular, {\mathbb{Q}} did not contain the measure of the hypotenuse of the unit square. It is now known that almost all the potential measuring values are missing from {\mathbb{Q}}.

These missing values lead to an important concept in mathematics, completeness. A number set is complete if any number, approximated arbitrarily closely by a sequence of numbers in the set, is also a number in the set. {\mathbb{Q}} is not complete because, e.g., {\sqrt{2}} can be approximated arbitrarily closely by rational numbers, but it is not a rational number. Completion of {\mathbb{Q}} thus involves constructing additional numbers, starting from the rational numbers, to fill in the spaces, and then demonstrating that the resulting number system is itself complete. The real numbers are typically constructed via Cauchy sequences or Dedekind cuts. Cauchy sequences have far reaching impact on mathematical analysis and need to be understood, although both methods are beyond the current scope.

Define {\mathbb{R}} to include both the rational and irrational numbers. The numbers in {\mathbb{R}} are simple enough to characterize as the totality of infinite decimals, where the numbers that end with infinite zeros are discarded as duplicates of the related numbers ending in infinite nines. {\mathbb{Q}} is the subset of infinite decimals that repeat after a while. The irrational numbers are the non-repeating decimals. But this characterization does not aid intuition about the kind of thing a real number is.

As a model for constructing irrational numbers out of the rational numbers, visualize nested intervals with rational endpoints on the number axis, each interval in succession having shorter length. Then the nested interval lengths tend to a limiting value of zero. There are two things to show, that every real number corresponds to such a nested interval sequence, and the limit of such a sequence is always a single point.

To show that every real number is represented in this construction, simply base the intervals on its decimal expansion. Start with 10 closed intervals whose endpoints are [0,.1], [.1, .2], {\ldots}, [.9, 1]. Then the first digit after the decimal point is in one of these intervals. Choose it and divide it into 10 intervals each 1/10 the size of the prior. The 2nd significant digit must be in one of these. Choose it and repeat indefinitely. To show that every such sequence corresponds to a point on the number line, observe that two distinct points will be separated by some distance, and as the intervals get smaller than that distance, one or the other must be excluded.

By this construction, a real number has no precise value, being an endless sequence; the number axis is a continuum of such sequences of diminishing intervals. Accepting {\mathbb{R}} as a set of such sequences, it is necessary to ask if they can be added and multiplied together, and compared. Yes, simply add or multiply or compare the rational endpoints of their intervals. For instance to add two sequences, simply add their start and end points respectively, a creating new interval sequence. Thus it is shown the rational numbers and irrational numbers use the same arithmetic.

In the end it is simpler to view real numbers as numbers and not sequences, another mathematical idealization. These idealizations are made concrete when they are ascribed precise geometric interpretations, as with {\pi}. Our physical reality appears continuous to us, particularly our concept of time, so that it is easy for our brains to imagine real numbers perhaps being expressive of reality. But physicists are coming to a quantized view of the physical spacetime we inhabit, centered on the Planck length. Results may be available within our lifetimes which prove that the continuum exists only in our heads. Grappling with the inverse reality, proving a finite or infinite universe, may take a while longer. Perhaps our physical existence will be eventually shown to be a type of hologram projected from an infinite flat universe. We will need some such unbounded scenario to admit a physical basis for the countably infinite.

Returning to a summary of the mathematical topic at hand, {\mathbb{Q}} is not complete. {\mathbb{R}} extends {\mathbb{Q}} by adding the irrational numbers, modeling these numbers by infinite sequences. In this sense, {\mathbb{R}} is the completion of {\mathbb{Q}}, but {\mathbb{R}} is not algebraically closed. {\mathbb{C}} extends {\mathbb{R}} by adding {i}, in the process expanding from the {x}-axis to fill the Cartesian plane. {\mathbb{C}} is both complete and algebraically closed.

This discussion will center on {\overline{\mathbb{Q}}}, a countable subset of {\mathbb{C}}. {\overline{\mathbb{Q}}} includes the algebraic numbers whose study is the aim of ANT. {\overline{\mathbb{Q}}} is the smallest algebraically closed field to contain {\mathbb{Q}}, and is hence the algebraic closure of {\mathbb{Q}}.

6. Equations and Varieties


Define a {\mathbb{Z}}-equation as a polynomial equation where all the coefficients are integers. Machinery will be developed to characterize solutions of systems of {\mathbb{Z}}-equations. Solving systems of equations is not the point of ANT. Rather, the structure of such a solution set is sought. There are different solution sets to {\mathbb{Z}}-equations depending on what number systems are allowed to supply values for the variables. An abstraction, called a variety, captures the structure of a solution set across the different number systems, {\mathbb{Z}}, {\mathbb{Q}}, {\mathbb{R}}, {\mathbb{C}},… Then advanced machinery of algebraic geometry and number theory can establish characteristics of this abstract structure. In particular, a solution set may be easier to analyze in some number system, and the machinery can relate this known structure to another solution set from a different number system. While this machinery is beyond the scope here, an intuitive exploration of the concept of a variety is offered, and several structurally interesting varieties will be introduced as the discussion unfolds.

Given a {\mathbb{Z}}-equation, let {S(\mathbb{Z})} be the set of solutions from {\mathbb{Z}}, {S(\mathbb{Q})} be the set of solutions from {\mathbb{Q}}, {\ldots}. Then {S} is a variety, the function associated with a {\mathbb{Z}}-equation or systems of {\mathbb{Z}}-equations, that assigns to any number system the set of solutions to the associated equation(s).

Shown are some values for such a variety S associated with the {\mathbb{Z}}-equation for a circle, {x^2+y^2=1}, where solutions are written {(x,y)}:

\displaystyle S(\mathbb{Z}) = \{(1,0), (-1,0),(0,1),(0,-1)\}

\displaystyle S(\mathbb{Q}) = \left\{\left(\dfrac{1-t^2}{1+t^2}, \dfrac{2t}{1+t^2}\right) : t \in \mathbb{Q} \right\}\bigcup \{(-1,0)\}

\displaystyle S(\mathbb{R}) = \{(\cos \theta, \sin \theta) : 0 \le \theta < 2\pi\}

\displaystyle S(\mathbb{C}) =\left \{ \left (z,\pm \sqrt{1-z^2} \right ) : z \in \mathbb{C} \right \}

\displaystyle S(\mathbb{F}_2) = \{ (1,0) (0,1) \}

\displaystyle S(\mathbb{F}_3) = \{ (1,0)(2,0)(0,1)(0,2) \}

\displaystyle S(\mathbb{F}_5) = \{ (1,0)(4,0)(0,1)(0,4) \}

\displaystyle S(\mathbb{F}_7) = \{ (1,0)(6,0)(0,1)(0,6)(2,2)(2,5)(5,2)(5,5) \}

Note that {x=1, y=0} is a solution in {S(\mathbb{Z})}. Since {1} and {0} are elements of all the number systems, {(1,0)} should appear in all other solution sets as well, as is clear from solution sets written discretely. For the other sets, observe for {S(\mathbb{Q})} that setting {t=0} produces {(1,0)}; for {S(\mathbb{R})}, setting {\theta = 0} produces {(1,0)}; for {S(\mathbb{C})}, setting {z=1} produces {(1,0)}.

As shown, systems of equations may have finite or infinite solutions. Some may have none at all. An example of no integer solutions was provided earlier: {x^2+y^2=11}.

Consider the set of {\mathbb{Z}}-equations:

\displaystyle x^2+y^2+z^2=w

\displaystyle w^4=1

\displaystyle x+y=z

Here there are no solutions in {\mathbb{Z}}, and infinite solutions in {\mathbb{R}}.

Systems of {\mathbb{Z}}-equations may have equivalent varieties. In the degenerate cases, all sets of inconsistent equations share the empty variety. All sets of equivalent equations share equivalent varieties. {\mathbb{Z}}-equations having equivalent varieties can be induced by variable substitution. For example,

\displaystyle x^3+y^3 = 0

\displaystyle z^3-3z^2y+3zy^2=0

represent equivalent equations under the invertible transformation {x=z-y}. The equations have different forms and use different variable values, but their varieties are equivalent. These are called isomorphic varieties, meaning literally that they have the same shape. When two systems of {\mathbb{Z}}-equations have isomorphic varieties, and one is easier to solve than the other, the structure of their common variety can serve to shed light on the more difficult solution set.

For the remainder, consideration is restricted to varieties of single {\mathbb{Z}}-equations in a single variable, such as {p(x)=x^3+x-2=0}. By the Fundamental Theorem of Algebra, a polynomial {p(x)} will have {n} roots where {n} is the degree of the polynomial. These roots correspond to the different solutions to {p(x)=0}.

Let S be the variety associated with {p(x)=0} above. By inspection, {p(1)=0}. By the Fundamental Theorem of Algebra, {p(x)} can be factored; here as {p(x)=(x-1)(x^2+x+2)}, where the second factor is solvable by the quadratic formula. In this case, this formula yields no integer solutions. Thus, {S(\mathbb{Z})=\{1\}}, and as above, all other solution sets for other number systems will also contain {1} as a solution.

The structure of {S(A)}, for number system {A}, is the subject of interest. The structure so far has been simple set structure, where the elements have been determined and their cardinality demonstrated. But it gets better. {S(A)} will be shown to define a representation of the Galois group, to be defined later along with interesting varieties.

Proceed to Quadratic Reciprocity, Galois Theory, Elliptic Curves

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s