quality:corruption
Products of prime powers

Let m = p 1 m 1 p 2 m 2 ⋯ p k m k = q 1 q 2 ⋯ q k {\displaystyle m=p_{1}^{m_{1}}p_{2}^{m_{2}}\cdots p_{k}^{m_{k}}=q_{1}q_{2}\cdots q_{k}} where p 1 < p 2 < ⋯ < p k {\displaystyle p_{1}<p_{2}<\dots <p_{k}} be the factorization of m {\displaystyle m} into prime powers. The group of units mod m {\displaystyle m} is isomorphic to the direct product of the groups mod the q i {\displaystyle q_{i}}:

This means that 1) there is a one-to-one correspondence between a ∈ (Z / m Z) × {\displaystyle a\in (\mathbb {Z} /m\mathbb {Z})^{\times }} and k {\displaystyle k} -tuples (a 1, a 2, …, a k) {\displaystyle (a_{1},a_{2},\dots,a_{k})} where a i ∈ (Z / q i Z) × {\displaystyle a_{i}\in (\mathbb {Z} /q_{i}\mathbb {Z})^{\times }} and 2) multiplication mod m {\displaystyle m} corresponds to coordinate-wise multiplication of k {\displaystyle k} -tuples:

The Chinese remainder theorem (CRT) implies that the a i {\displaystyle a_{i}} are simply a i ≡ a (mod q i). {\displaystyle a_{i}\equiv a{\pmod {q_{i}}}.}

There are subgroups G i < (Z / m Z) × {\displaystyle G_{i}<(\mathbb {Z} /m\mathbb {Z})^{\times }} such that

Then (Z / m Z) × ≅ G 1 × G 2 ×... × G k {\displaystyle (\mathbb {Z} /m\mathbb {Z})^{\times }\cong G_{1}\times G_{2}\times...\times G_{k}} and every a ∈ (Z / m Z) × {\displaystyle a\in (\mathbb {Z} /m\mathbb {Z})^{\times }} corresponds to a k {\displaystyle k} -tuple (a 1, a 2,... a k) {\displaystyle (a_{1},a_{2},...a_{k})} where a i ∈ G i {\displaystyle a_{i}\in G_{i}} and a i ≡ a (mod q i). {\displaystyle a_{i}\equiv a{\pmod {q_{i}}}.} Every a ∈ (Z / m Z) × {\displaystyle a\in (\mathbb {Z} /m\mathbb {Z})^{\times }} can be uniquely factored as a = a 1 a 2... a k. {\displaystyle a=a_{1}a_{2}...a_{k}.}

If χ m, _ {\displaystyle \chi _{m,\_}} is a character mod m, {\displaystyle m,} on the subgroup G i {\displaystyle G_{i}} it must be identical to some χ q i, _ {\displaystyle \chi _{q_{i},\_}} mod q i {\displaystyle q_{i}} Then

showing that every character mod m {\displaystyle m} is the product of characters mod the q i {\displaystyle q_{i}}.

For (t, m) = 1 {\displaystyle (t,m)=1} define

Then for (r s, m) = 1 {\displaystyle (rs,m)=1} and all a {\displaystyle a} and b {\displaystyle b}