Library of Mathexandria

Lemma: Suppose that $(a,m)=1$, then the least residues of $ka$ for $k=1, \ldots, m-1$ are a permutation of $0,1, \ldots, m-1$.  Proof) There are $m-1$ numbers in $\mathbb{Z}/m\mathbb{Z}$ that is not congruent to $0$. Let $ka$ and $k'a$ be two numbers with $1 \leq k, k' \leq m-1$, then we have $(k-k')a \equiv 0$ implies that $(k-k') \equiv 0$ as $(a, m)=1$, however because $-m < k-k' < m$, we see that $k=k'$. Hence there cannot be two different $k, k'$ with different least residue. Thoerem (Fermat's Little Theorem): If $p$ is prime and $(a,p)=1$, then $a^{p-1} \equiv 1 ~(\bmod{~p})$ Proof) Given any $p$, a prime, we know that $(a,p) = 1$. Hence  $a, 2a, \ldots, (p-1)a$ all have different least residues which would be $1, \ldots, p-1$. If we multiply them together, $(p-1)!  \equiv a^{p-1}(p-1)!$ as $(a, l) = 1$ for $l=1, \ldots, p-1$, we may conclude that $a^{p-1} \equiv 1~(\bmod{~p})$. Easy application of Fermat's Little Theorem would be, Cor...

From the previous post, we have considered $Hom_R(B, -)$, but this time we want to consider $Hom_R(-,A)$. Instead of getting a covariant functor, we now get a contravariant functor (i.e. reverses the map). Consider a map $f: P_1 \rightarrow P_2$, then the natural way to pass it to Hom-sets are as follows, $f^*: Hom_R(P_2, A) \rightarrow Hom_R(P_1, A) (\dagger)$ $\phi \mapsto \phi \circ f$ If we try to construct the order way,  $Hom_R(P_1, A) \rightarrow Hom_R(P_2, A)$ $\phi \mapsto \phi \circ f$? $\phi \mapsto f \circ \phi$? Both composition would not make sense, hence we take $(\dagger)$ as our $Hom_R(-,A)$ functor. And obviously $R$-module $A$, $P$ is sent to $Hom_R(P,A)$. We now prove that $Hom_R(-,A)$ functor is again a left-exact functor, which means the following, Given a short exact sequence, $0 \rightarrow P_1 \stackrel{f}{\rightarrow} P_2 \stackrel{g}{\rightarrow} P_3$ $0 \rightarrow Hom_R(P_3,A) \stackrel{g^*}{\rightarrow} Hom_R(P_2, A) \stackrel{f^*}{\rightarrow} Hom_R(...

A profinite group  is an inverse limit of finite groups. Let $I$ be a directed set respect to a relation $\leq$, where $\leq$ is reflexive and transitive and for every $i_1, i_2 \in I$, then there exists $i$ such that $i \geq i_1$ and $i \geq i_2$. An inverse system  of topological spaces over $I$ is denoted $(I, G_i, \pi_i^j)$ where for each $i \in I$, $G_i$ is a topological space and for $i \leq j$, there exists a morphism $\pi_i^j :G_j \rightarrow G_i$ with $G_i^i$ being the identity. Also, if we have $i \leq j \leq k$, then then composition $\pi_i^j \pi^k_j = \pi^k_i$. Often we call it $(G_i)$. Example : Consider $\mathbb{Z}/p^i \mathbb{Z}$ with usual $\leq$ of integers. The morphism $\pi_i^j$ for $i \leq j$ is the natural projection $\mathbb{Z}/p^j \mathbb{Z} \twoheadrightarrow \mathbb{Z}/p^i \mathbb{Z}$. Then it is easily followed that the composition is followed.  We can view finite groups as a topological space by giving them the discrete topology (i.e. every su...

Let $\mathbb{Q}$ be the field of rational numbers. A number field is a finite extension of $\mathbb{Q}$. Algebraic number theory is a one of the fields in mathematics which studies number field, as problems in $\mathbb{Q}$ becomes a easier  problem when lifted to a number field. The next post will include an example of such. The reason why we consider $\mathbb{Q}$ in number theory is because it is the quotient field of $\mathbb{Z}$, so we generalize the concept of integers by the following method. The materials are from Prof. Elman's Lecture Notes, Lang's Algebraic Number Theory, Neukirch's Algebraic Number Theory, and Marcus's Number Fields. Let $B$ be a commutative ring an extension of a ring $A$ (i.e. $A \subset B$), then an element $x \in B$ is called integral over $A$ if there exists a monic polynomial $f \in A[t]$ such that $f(x)= 0$. Proposition : With the same assumption as above, the following are equivalent         1) $x \in B$ is integral over $A$ ...

Let $V$ be a finite dimensional vector space over $F$ and $T$ be a linear operator on $V$. If $\beta$ an ordered basis of $V$, then we want to establish the following in this post: Let $f$ be the characteristic polynomial of $T$, then $f(t) = t^n -(tr(T))t^{n-1} + \cdots + (-1)^n det(T)$ Let's recall the definition of the characteristic polynomial of $T$,  $f(t) = det(T - tI)$ where $I$ is the appropriate identity transformation. If $F$ is itself not algebraically closed, we consider $\overline{F}$, the algebraic closure of $F$, then $f(t)$ splits with the form, $f(t) = \prod_{i=1}^n (t-\lambda_i)$ Since we are working on $\overline{F}$, we could find the Jordan Canonical form of $T$, hence in a matrix language $[T]_\beta = QAQ^{-1}$ where $A$ is a upper-triangular matrix with diagonal being eigenvalues. Then $det(T) = det(QAQ^{-1}) = det(A)$ which is the product of the eigenvalues. (up to a sign) Similiarly, we have that $tr(T) = tr(A) = \sum \lambda_i$, hence coincide ...

As $\mathbb{Z}$ is infinite, we would like to look at the numbers " smaller " than the integers in which contains a " local " data of the integers. Before we even discuss what this means, let's fix $m$, an integer. Let $n$ be any integer, then by the division algorithm, there exists unique $q,r$ such that $n=mq+r$, then consider a situation there $n = r$. For instance if $n=7$ and $m=3$, then $7 = 2 \cdot 3 +1$, hence $1 = 7$. If we have a set $A$ and we give an equivalence relation on the set by $a \sim b$ if the following conditions hold:      1) $a \sim a$      2) $a \sim b$, then $b \sim a$      3) $a \sim b$ and $b \sim c$ then $a \sim c$. For instance, $=$ on $\mathbb{Z}$ would give an equivalence relation. Now we consider a new equal, or the equivalence relation $\equiv ~(\bmod{m})$ where $a \equiv b ~(\bmod{m})$ if $m|a-b$ or, in order words, $a$ and $b$ have the same remainder. Consider $[n]_m$ be the set of all elements in $\m...

For equations like $x^2+y^2 = 1$ and $3x + 4y = 8$, it is easy to find a solution satisfying the equations when $(x,y)$ are reals. Actually there are infinitely many solutions to both equations $x^2 + y^2 = 1$ and $3x+4y = 8$. However, if we restrict our solutions to certain number, e.g. rational numbers, integers, and positive integers, then the equation might have finite solutions or no solution. If we restrict our self to rational numbers, integers and positive integers, then we call the equation to be diophantine equations . In today's post we observe the linear diophantine equation, $ax+by=c$ where $a,b, c \in \mathbb{Z}$.  From now on, the solution is assumed to be integers. Lemma 1 : If $x_0, y_0$ is a solution to $ax+by=c$, then so is $x_0-bt, y_0+at$  for all integer $t \in \mathbb{Z}$. Proof) It is clear that $ab - ba = 0$, hence $-b, a$ becomes the solution to the equation $ax+by = 0$ Hence multiplying $t$ on both side we have that the solution is of the ...

In this post, we prove the well-used property that the Hom functor is left-exact. We consider the Hom functor of the following form $Hom_R(B,-)$ which is a functor from $R-mod$ the category of $R$-modules to $Ab$ the category of abelian groups. The functor contains the following data: $A \mapsto Hom_R(B,A)$ $\{ f: A \rightarrow A' \} \mapsto \{ f^*: Hom_R(B,A) \rightarrow Hom_R(B,A') \}$ where $f^*$ is defined by $f^*(\phi) = f \circ \phi$. Then we see that Hom functor is a covariant functor.   Proof) If $f : A \rightarrow A$ is the identity map, then $f^*(\phi) = f \circ \phi = f$, hence $f^*$ also becomes an identity map of $Hom_R(B,A)$. Also, let $f : A \rightarrow A'$ and $g: A' \rightarrow A''$, then we see that  $(g \circ f)^*(\phi) = (g \circ f) \circ \phi  = g \circ (f \circ \phi) = g \circ (f^*(\phi)) = (g^* \circ f^*)(\phi)$.  i.e. $Hom_R(-,B)$ is a covariant functor. Now to our main point that $Hom_R(B,-)$ is left-exact. A functor $\mathcal{F}$ is le...

A prime number is an integer $p$ such that $p>1$ and $p = ab$ then either $a=1$ or $b=1$ (1) This says that prime numbers cannot be decomposed into smaller pieces. There is an equivalent definition of primes: $p|ab \Rightarrow p|a$ or $p|b$ (2) In abstract algebra, an element $p$ is called a prime if (2) holds, and $p$ is called an irreducible if (1) holds. Our main focus of this chapter is to prove that $\mathbb{Z}$ is a unique factorization ring (or more specifically Unique factorization domain). And it is well-known that in UFD, prime elements and irreducible elements coincide. Proposition : Let $p$ satisfies (1) if and only if $p$ satisfies (2) Proof) Suppose $p|ab$, then $(p,a) = 1$, then $p|b$ by the previous posts. If $(p,a) = p$, then $p|a$ hence the result. Conversely, for the sake of contradiction that there exists two divisors $1<d_1, d_2<p$, not necessarily distinct. Then $p | d_1 d_2 \Rightarrow p| d_1$ or $p|d_2$, which cannot happen. Lemma 1:  Every integer...

Calculating the greatest common divisor of two large numbers make take too much time without a proper algorithm. The following algorithm is central in number theory because it provides an important characteristic of the greatest common divisor Theorem : (The division algorithm) Given positive integers, $a,b$ with $b \neq 0$, there exist  unique  $q$ and $r$ such that $a = qb +r$ with $0 \leq r < b$. Proof) Let $S = \{ a - qb ~|~ q \in \mathbb{Z}\} \cap \mathbb{Z}^{\geq 0}$, then we have $a \in S$, so the set $S$ is nonempty. $\mathbb{Z}^{\geq 0}$ is the set of all non-negative integers. Also $S$ is bounded below $0$ because by our construction. By the well-ordering principle, there exists a minimal element $a-qb$ for some $q \in \mathbb{Z}$. Let $r = ab-q$ and suppose $r \geq b$, then we have $ab - q \geq b \Rightarrow a(b-1) -q \geq 0$, hence $a(b-1) - q \in S$ which contradicts the minimality of $r$. Hence $0 \leq r < b$. Now for uniqueness, consider if there exi...

Elementary Number Theory is study of the integers $\mathbb{Z}$ without using techniques from other fields such as real and complex analysis, algebra, and topology. The subject does not assume any prerequisites other than mathematical fundamentals such as elementary set theory. The notes are based on the course that I am currently taking in UCLA from professor Chandrashekhar Khare . This series will heavily follow: Underwood Dudley, Elementary Number Theory. ( Amazon )   Definition: $a,b \in \mathbb{Z}$, then we say that $a$ divides $b$, or $b$ is divided by $a$ if there exists $c \in \mathbb{Z}$ such that $ac = b$ and denote it $a|b$. Example :       1) $12|60$ because $5 \cdot 12 = 60$      2) $3 \not \mid 10$      3) $a|0$ for all $a \in \mathbb{Z}$ as $0 = 0 \cdot a$. Lemma : If $d|a$ and $d|b$, then $d|a+b$. Proof) There exist $c_1, c_2$ such that $c_1d = a, c_2d = b$. Adding the two equations we get $d(c_1+c_2) | a+b$. As...