Abstract Nonsense

Crushing one theorem at a time

The Chinese Remainder Theorem (Pt. II)


Point of Post: This is a continuation of this post.

\text{ }

Let’s see if we can give an example of the CRT which doesn’t involve \mathbb{Z}. In particular, we shall show that the CRT can help identify F[x] mod certain ideals. In particular, we have the following

\text{ }

Theorem: Let F be a field and z_1,\cdots,z_n\in F be n-distinct non-zero numbers. Then, F[x]/[(x-z_1)\cdots (x-z_n)]\cong F^n (where the denominator is the product of the ideals (x-z_1),\cdots,(x-z_n) not the ideal generated by (x-z_1)\cdots(x-z_n) although, this is a completely artificial distinction, since, they are equal).

Proof: What we claim first is that (x-z_i),(x-z_j) are coxmaximal for each distinct i,j\in[n]. Indeed, we merely note that \displaystyle x-z_i+-(x-z_j)=z_i-z_j\in (x-z_i)+(x-z_j) and since z_i-z_j\ne 0 we have that z_i-z_j is a unit and so (x-z_i)+(x-z_j)=F[x]. It thus frollows from the CRT that F[x]/[(x-z_1)\cdots (x-z_n)]\cong F[x]/(x-z_1)\times\cdots\times F[x]/(x-z_n). That said, recall that F[x]/(x-z_j)\cong F by the first isomorphism theorem and the epimorphism p\mapsto p(z_n) (we technically don’t know that p(x) has a zero at z_j implies that p is divisible by x-z_j, but it’ll soon be proven, and not hard to believe). The conclusion follows. \blacksquare

\text{ }

Corollary: Let a_1x-z_1,\cdots,a_nx-z_n\in F[x] be such that \displaystyle a_1,\cdots,a_n are non-zero and \displaystyle \frac{z_1}{a_1},\cdots,\frac{z_n}{a_n} are distinct numbers. Then, F[x]/[(a_1x-z_1)\cdots(a_nx-z_n)]\cong F^n.

Proof: Merely note that \displaystyle (a_jx-z_j)=\left(a_j(x-\frac{z_j}{a_j})\right)=\left(x-\frac{z_j}{a_j}\right). \blacksquare

\text{ }

\text{ }

Number Theoretic Implications

Not only does the CRT have important pure ring theoretic implications but it also implies a few classic number theoretic facts. Most obviously is the refinement of the one given in the motivation of this post:

\text{ }

Theorem: Let n_1,\cdots,n_m be pairwise coprime numbers in \mathbb{Z}. Then, the system of simultaneous linear equations

\text{ }

\left\{\begin{array}{c}x\equiv a_1\text{ mod }n_1\\ \vdots\\ x\equiv a_m\text{ mod }n_m\end{array}\right\}

\text{ }

has a solution x\in\mathbb{Z} which is unique modulo n_1\cdots n_m.

\text{ }

That said, it has much more satisfying, applicable number theoretic applications. For example:

\text{ }

Theorem: Let n be a natural number with prime factorization p_1^{a_1}\cdots p_m^{a_m} and P(x)\in\mathbb{Z}[x]. Then, the equation P(x)\equiv 0\text{ mod }n has a solution if and only if P(x)\equiv 0\text{ mod }p_j^{a_j} has a solution for each j=1,\cdots,m. Moreover, if N_k(P) (for some generic integer k) denotes the number of solutions P(x)\equiv 0\text{ mod }k then N_P(n)=N_P(p_1^{a_1})\cdots N_P(p_m^{a_m}).

\text{ }

Indeed, this follows immediately from the CRT used in conjunction with following lemma:

\text{ }

Theorem: Let R and S be rings and a_0+\cdots+a_nx^n=P(x)\in R[x] then if f:R\to S is a monomorphism and Q(x)\in S[x] is given by Q(x)=f(a_0)+\cdots+f(a_n)x^n then the map F:\mathbb{V}_R(P)\to\mathbb{V}_S(Q) (where \mathbb{V}_R(P)=\left\{x\in R:P(x)=0\right\} and \mathbb{V}_S(Q) is defined similarly) given by x\mapsto f(x) is an injection.

Proof: To see that F is really well-defined (in the sense that F maps \mathbb{V}_R(P) into \mathbb{V}_S(P)) we merely note that if P(x)=0 then f(P(x))=0, but since f is a morphism, we know that f(P(x))=P(f(x)) and so P(f(x))=0. Since f is injective evidently we have that F is injective. \blacksquare

\text{ }

Corollary: Since evidently if f is an isomorphism the map G:\mathbb{V}_S(P)\to\mathbb{V}_R(P) given by x\mapsto f^{-1}(x) is a two-sided inverse to F we have that if f is an isomorphism then \#(\mathbb{V}_R(P))=\#(\mathbb{V}_S(P)).

\text{ }

To see why this proves the stated theorem we first note that since (P(x_1),\cdots,P(x_n)) equals (by definition) P((x_1,\cdots,x_n)) and so

\text{ }

\#(\mathbb{V}_{\mathbb{Z}/(p_1^{a_1})\times\cdots\times\mathbb{Z}/(p_m^{a_m})}(P))=\#(\mathbb{V}_{\mathbb{Z}/(p_1^{a_1})}(P))\times\cdots\times\#\mathbb{V}_{\mathbb{Z}/(p_m^{a_m})}(P))=N_P(p_1^{a_1})\cdots N_P(p_m^{a_m})

\text{ }

But, by the above corollary since \mathbb{Z}/(n)\cong\mathbb{Z}/(p_1^{a_1})\times\cdots\times\mathbb{Z}/(p_m^{a_m}) we have that

\text{ }

N_P(n)=\#(\mathbb{V}_{\mathbb{Z}/(n)}(P))=\#(\mathbb{V}_{\mathbb{Z}/(p_1^{a_1})\times\cdots\times\mathbb{Z}/(p_m^{a_m})})

\text{ }

From where the second assertion of the theorem follows. The first assertion is immediate from the second  since it clearly is equivalent to N_P(n)=0 if and only if N_P(p_1^{a_1})=\cdots=N_P(p_m^{a_m})=0.

\text{ }

\text{ }

References:

1. Dummit, David Steven., and Richard M. Foote. Abstract Algebra. Hoboken, NJ: Wiley, 2004. Print.

2. Bhattacharya, P. B., S. K. Jain, and S. R. Nagpaul. Basic Abstract Algebra. Cambridge [Cambridgeshire: Cambridge UP, 1986. Print.

 

Advertisements

September 6, 2011 - Posted by | Algebra, Ring Theory | , , , , , , , ,

1 Comment »

  1. […] Chinese Remainder Theorem (Pt. III) Point of Post: This is a continuation of this post. […]

    Pingback by Chinese Remainder Theorem (Pt. III) « Abstract Nonsense | September 6, 2011 | Reply


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

%d bloggers like this: