Chinese remainder theorem induction

Question

I came across this somewhere,

An important consequence of the chinese remainder theorem is that when studying modular arithmetic in general, we can first study modular arithmetic a prime power and then appeal to the Chinese Remainder Theorem to generalize any results. For any integer $n$, we factorize $n$ into primes $n=p_{1}^{k_1}\dots p_{m}^{k_m},$ and then use the Chinese Remainder Theorem to get

$$ℤ_n=ℤ_{p_{1}^{k_1}}×\cdots ×ℤ_{p_{m}^{k_m}}$$

To prove statements in $ℤ_{{p}^{k}}$, one starts from $ℤ_{{p}}$, and inductively works up to $ℤ_{{p}^{k}}$. Thus the most important case to study is $ℤ_{{p}}$.

Can someone help me do the induction on this?

Answer 1

Suppose you want to find the last 2 digits of $2^{80}$ i.e. what is $2^{80} \pmod {100}$ The Chinese remainder theorem says to look at:

$2^{80} \pmod {2},2^{80} \pmod {5}, 2^{80} \pmod {4}, 2^{80} \pmod {25}$

$2^{80} 4^{40}\equiv 0 \pmod {4}$

$2^{4} \equiv 1\pmod {5}$ Fermat little theorem

$2^{20} \equiv 1\pmod {25}$

We need a number that equals $1$ when divided by $25$ and $0$ when divided by $4,$ and is less than $100.$

$76$

Answer 2

You need to show that if all primes $p_1$ to $p_m$ are distinct then the ideals $p_{i}^{a_i}\mathbb{Z}$ and $p_{j}^{a_j}\mathbb{Z}$ are comaximal, for all $i\neq j$, that is we can say $p_{i}^{a_i}\mathbb{Z}+p_{j}^{a_j}\mathbb{Z}=\mathbb{Z}$ (due to the fact there exist integers $a$, $b$ s.t. $p_ia+p_jb=1$). Then the map $$\mathbb{Z}\rightarrow (\Bbb{Z}/p_1^{a_1}\Bbb{Z})\times (\Bbb{Z}/p_2^{a_2}\Bbb{Z})\times\dotsm\times(\Bbb{Z}/p_{m}^{a_m}\Bbb{Z})$$ is a surjection, with kernel $$p_{1}^{a_1}\Bbb{Z}\cap p_{2}^{a_2}\Bbb{Z}\cap\dotsm \cap p_{m}^{a_m}\Bbb{Z} =p_{1}^{a_1}\Bbb{Z}\cdot p_{2}^{a_2}\Bbb{Z}\dotsm p_{m}^{a_m}\Bbb{Z} $$ hence \begin{align*} \Bbb{Z}/(p_{1}^{a_1}\Bbb{Z} p_{2}^{a_2}\Bbb{Z} \dotsm p_{m}^{a_m}\Bbb{Z} ) &=\mathbb{Z}/(p_{1}^{a_1}\Bbb{Z} \cap p_{2}^{a_2}\Bbb{Z} \cap\dotsm\cap p_{m}^{a_m}\Bbb{Z} )\\ &\cong(\mathbb{Z}/p_{1}^{a_1}\Bbb{Z}) \times (\mathbb{Z}/p_{2}^{a_2}\Bbb{Z})\times\dotsm\times(\mathbb{Z}/p_{m}^{a_m}\Bbb{Z}) \end{align*}

First do this for two prime powers, $p_1^{a_1}$ and $p_2^{a_2}$. Consider the map $$\sigma : \mathbb{Z}\longrightarrow(\mathbb{Z}/p_{1}^{a_1}\Bbb{Z}) \times (\mathbb{Z}/p_{2}^{a_2}\Bbb{Z})$$ defined by $$\sigma(z)=(z\,\operatorname{mod}p_1^{a_1},\ z\,\operatorname{mod} p_2^{a_2})$$ with $z\pmod{p_1^{a_1}}$ meaning the class in $\mathbb{Z}/p_{1}^{a_1}\Bbb{Z}$ containing $z$. For brevity define $A=p_{1}^{a_1}\Bbb{Z}$ and $B=p_{2}^{a_2}\Bbb{Z}$. We have $\sigma$ is a ring homomorphism, projecting $\Bbb{Z}$ into the two components $\Bbb{Z}/A$ and $\Bbb{Z}/B$ of the direct product.

The kernel of the homomorphism are the elements $e\in\Bbb{Z}$ that are in both of the ideals $A$, and $B$: $\ker(\sigma)=A\cap B$.

Since the $\gcd(p_1,p_2)=1$, the ideals $A$ and $B$ are comaximal. Hence there are elements $x\in A$ and $y\in B$ s.t. $x+y=1$. Thus $$\sigma(x)=(x\,\operatorname{mod}p_1^{a_1},\ 1-y\,\operatorname{mod}p_2^{a_2})=(0,1),$$ $$\sigma(y)=(1-x\,\operatorname{mod}p_1^{a_1},\ y\,\operatorname{mod}p_2^{a_2})=(1,0).$$ Now if $(z_1\,\operatorname{mod}p_1^{a_1},\ z_2\,\operatorname{mod}p_2^{a_2})$ is an arbitrary element of $\Bbb{Z}/A\times \Bbb{Z}/B$, then the element $z_2x+z_1y$ maps under $\sigma$ to: \begin{align*} \sigma(z_2x+z_1y)&=\sigma(z_2)\,\sigma(x)+\sigma(z_1)\,\sigma(y)\\ &=(z_2\,\operatorname{mod}p_1^{a_1},\ z_2\,\operatorname{mod}p_2^{a_2})\,(0,1)+(z_1\,\operatorname{mod}p_1^{a_1},\ z_1\,\operatorname{mod}p_2^{a_2})\,(1,0)\\ &=(0,\ z_2\,\operatorname{mod}p_2^{a_2})+(z_1\,\operatorname{mod}p_1^{a_1},0)\\ &=(z_1\,\operatorname{mod}p_1^{a_1},\ z_2\,\operatorname{mod}p_2^{a_2}) \end{align*} Hence $\sigma$ is surjective. We always have the ideal $AB\subseteq A\cap B$. Since $A$ and $B$ are comaximal we can show the reverse inclusion: let $x\in A$ and $y\in B$ s.t. $x+y=1$, then if $c\in A\cap B$, we have $c=cx+cy\in AB$, and $A\cap B\subseteq AB$. This proves the case for the two ideals $A$ and $B$.

Now for the induction, which follows from the case of two ideals: Let $A_1=p_{1}^{a_1}\Bbb{Z}$ and $A_2\dotsm A_m=p_{2}^{a_2}\Bbb{Z}\dotsm p_{m}^{a_m}\Bbb{Z}$. These are two ideals $A_1$ and $A_2\dotsm A_m$, which are comaximal. To see this let $x_i\in p_{1}^{a_1}\Bbb{Z}$ and $y_i\in p_{i}^{a_i}\Bbb{Z}$ s.t. $x_i+y_i=1$, $i\in\{2,3,\dotsc,m\}$, with $x_i+y_i\equiv y_i\pmod{p_1^{a_1}}$, and so $1=(x_2+y_2)(x_3+y_3)\dotsm(x_m+y_m)$ is an element in $p_{1}^{a_1}\Bbb{Z}+(p_{2}^{a_2}\Bbb{Z}\dotsm p_{m}^{a_m}\Bbb{Z})=\Bbb{Z}$.

Then if the prime factorisation of $n$ is $n=p_{1}^{a_1}p_{2}^{a_2}\dotsm p_{m}^{a_m}$, the factorisation of the ring $\Bbb{Z}/n\Bbb{Z}$ into a direct product of the rings of integers modulo the prime factors is the ring isomorpism: $$\Bbb{Z}/n\Bbb{Z}\cong (\Bbb{Z}/p_1^{a_1}\Bbb{Z})\times (\Bbb{Z}/p_2^{a_2}\Bbb{Z})\times\dotsm\times(\Bbb{Z}/p_{m}^{a_m}\Bbb{Z})$$ As multiplicative groups we also have the isomorphism: $$(\Bbb{Z}/n\Bbb{Z})^{\times}\cong (\Bbb{Z}/p_1^{a_1}\Bbb{Z})^{\times}\times (\Bbb{Z}/p_2^{a_2}\Bbb{Z})^{\times}\times\dotsm\times(\Bbb{Z}/p_{m}^{a_m}\Bbb{Z})^{\times}$$ whose order is given by: $$\phi(n)=\phi(p_1^{a_1})\phi(p_2^{a_2})\dotsm\phi(p_m^{a_m})$$ where $\phi$ is the Euler totient function, and $\phi(p^a)=p^{a-1}(p-1)$.

Answer 3

It would be more accurate to say $ℤ_n \cong ℤ_{p_{1}^{k_1}}×\cdots ×ℤ_{p_{m}^{k_m}}$ as the left and right sides are isomorphic to each other, not equal.

By $``$inductively works up to $\mathbb Z_{p^k}"$, the author suggests that you first solve the problem for $\mathbb Z_p$, then for $\mathbb Z_{p^2}$, and so on until, eventually, you see a pattern which you can state as an hypothesis. Then, hopefully, you can then prove that hypothesis using induction.

Exactly what the induction is will depend almost entirely on the problem you are trying to solve. So, without an actual problem, there is no way we can tell you how to do the induction.