Is my reasoning with regard to the Chinese Remainder Theorem correct?

51 Views Asked by At

Using the Chinese Remainder Theorem, for any set of $n$ primes (where $p_n\#$ is the primorial for the $n$th prime), there exists a unique solution such that:

$$\sum_{i=1}^{n}\,c_i\left(\frac{p_n\#}{p_i}\right) \equiv 1 \pmod {p_n\#}$$

where each $0 \le c_i < p_i$ and each $p_i$ represents the $i$th prime.

Further, it follows that for any integer $x$:

$$x\sum_{i=1}^{n}\,c_i\left(\frac{p_n\#}{p_i}\right) = \sum_{i=1}^{n}\,{x}c_i\left(\frac{p_n\#}{p_i}\right) \equiv x \pmod {p_n\#}$$

Now, let's say that I am evaluating the following expression:

$$\sum_{i=1}^n \,d_i\left(\frac{p_n\#}{p_i}\right)$$

Let's assume that I can show that for some $i$, $d_i \not \equiv yc_i \pmod {p_i}$ where $y$ is any integer.

Does it now follow that I have shown that:

$$\sum_{i=1}^n \,d_i\left(\frac{p_n\#}{p_i}\right) \not \equiv y \pmod {p_n\#}$$

My goal here is to see if this line of analysis is valid and whether there is any value in using these negative type of reasonings with regard to the Chinese Remainder Theorem.

1

There are 1 best solutions below

0
On BEST ANSWER

This is an interesting question. What you stated in your resulting inequality is correct.

Let $j$ be the prime index where your stated inequality holds, i.e., we have

$$d_j \not\equiv yc_j \pmod {p_j} \tag{1}\label{eq1A}$$

Next, for

$$\sum_{i=1}^n \, d_i\left(\frac{p_n\#}{p_i}\right) \equiv y \pmod{p_n\#} \tag{2}\label{eq2A}$$

to actually be true requires the congruence to hold for each prime factor of $p_n\#$, i.e., it also requires

$$\sum_{i=1}^n \, d_i\left(\frac{p_n\#}{p_i}\right) \equiv y \pmod{p_j} \tag{3}\label{eq3A}$$

Since all of the terms in the summation are congruent to $0$ modulo $p_j$ except for the $j$'th term, this gives

$$d_j\left(\frac{p_n\#}{p_j}\right) \equiv y \pmod{p_j} \tag{4}\label{eq4A}$$

Multiplying both sides by $c_j$, and using that $c_j$ is defined so that $c_j\left(\frac{p_n\#}{p_j}\right) \equiv 1 \pmod{p_j}$, we get

$$\begin{equation}\begin{aligned} d_j\left(c_j\left(\frac{p_n\#}{p_j}\right)\right) & \equiv yc_j \pmod{p_j} \\ d_j & \equiv yc_j \pmod{p_j} \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

However, this contradicts the required condition in \eqref{eq1A}. This means \eqref{eq2A} is not true, i.e., the congruence there is an inequality instead.