Chinese Remainder Theorem and reduced system of residues

Question

I need help understanding the following statement:

If $\gcd(a,q)=1$ then by the Chinese Remainder Theorem, $\frac{a}{q}$ has a unique representation modulo 1 of the form $$\sum_{p}\frac{a(p^u)}{p^u}$$ where $a(p^u)$ is a reduced residue modulo $p^u$.

I don't understand how the Chinese Remainder Theorem tells us this, and moreover I am quite confused by what this notation even means. Can anyone help by providing an example of what this means? Moreover I want to modify this statement to the following:

In the case $\gcd(a,q)\ne 1$, how many representations modulo 1 are there of the form $$\frac{a}{q}=\sum_p\frac{a(p^u)}{p^u}?$$

Answer 1

Write the prime factorisation of $q$ as $q=\prod_p p^u$

Now consider the expression $$\sum_p\frac{a(p^u)}{p^u}$$ Making the denominator $q$ gives $$\sum_p\frac{a(p^u)}{p^u} = \sum_p\frac{a(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}}{q} = \frac{\sum_pa(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}}{q}\pmod 1$$ And now instead of this we look at $$\sum_pa(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}\pmod q.$$ For each $p$ we have that this expression equals $a(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}\pmod {p^u}$ because all other terms are a multiple of $p^u$. Furthermore, $\mathrm{gcd}\left(p^u,\prod_{\hat p\neq p}\hat p^{\hat u}\right)=1$ so there is some number $x_p$ such that $x_p\prod_{\hat p\neq p}\hat p^{\hat u}=1\pmod{p^u}$. When one chooses $a(p^u)=ax_p\pmod {p^u}$, one thus sees that $a(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}=a\pmod{p^u}$.

Now one uses the Chinese remainder theorem: When for each $p$ one has $\sum_p a(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}=a\pmod{p^u}$, then this theorem states that $\sum_p a(p^u)\prod_{\hat p\neq p}\hat p^{\hat u}=a\pmod{q}$.

Lastly, the numbers $a(p^u)$ are unique when one requires $0\leq a(p^u)<p^u$ per construction.

I hope this helps!

EDIT:

For example, say $q=5040=2^4\cdot 3^2\cdot 5\cdot 7=16\cdot9\cdot7\cdot5$ and $a=2431=11\cdot13\cdot17$. Note that $\mathrm{gcd}(a,q)=1$.

Now we should find numbers $a(p^u)$ for $p^u\in\{2^4,3^2,5,7\}$ such that $$\frac{a}{q}=\sum_p\frac{a(p^u)}{p^u}\pmod{1}$$

Following the procedure above, these numbers can be found by calculating:

• $9\cdot7\cdot5=11\pmod{16}$ and $11\cdot3=1\pmod{16}$ so $x_2=3$ and $a(2^4)=a\cdot3=2431\cdot3=13\pmod{16}$
• $16\cdot7\cdot5=2\pmod 9$ and $5\cdot2=1\pmod 9$ so $x_3=5$ and $a(3^2)=a\cdot5=2431\cdot5=5\pmod 9$
• $16\cdot9\cdot5=6\pmod 7$ and $6\cdot6=1\pmod 7$ so $x_7=6$ and $a(7^1)=a\cdot6=2431\cdot6=5\pmod 7$
• $16\cdot9\cdot7=3\pmod 5$ and $2\cdot3=1\pmod 5$ so $x_5=2$ and $a(5^1)=a\cdot2=2431\cdot2=2\pmod 5$

In summary, we have found $a(2^4)=13$, $a(3^2)=5$, $a(7^1)=5$ and $a(5^1)=2$

Indeed, we can calculate $$\frac{13}{16}+\frac{5}{9}+\frac{5}{7}+\frac{2}{5}=\frac{12511}{5040}=2+\frac{2431}{5040}=\frac{2431}{5040}\pmod1$$