D.10 Chinese remainder packet refinement
On this page · Permalink · Source line 2967
The Chinese remainder theorem gives an exact factorization of residue addresses. We state it at the level of sequence projectors so that it can be combined directly with the earlier coordinate systems.
Historical definition D.105: Residue projector
For a sequence \(a=(a_n)_{n\geq0}\), a positive integer \(N\), and an address \(r\) modulo \(N\), define
Historical proposition D.106: Complete residue packet system
For fixed \(N\), the projectors \(P_{N,r}\) satisfy
and
Proof
Every nonnegative integer belongs to exactly one residue class modulo \(N\).
Historical theorem D.107: Coprime packet factorization
Let \(A\) and \(B\) be coprime positive integers. Let \(r_A\) be an address modulo \(A\) and \(r_B\) an address modulo \(B\). Let \(r\) be the unique address modulo \(AB\) satisfying
Then
Proof
The product retains exactly the indices satisfying both congruences. By the Chinese remainder theorem, those indices form one residue class modulo \(AB\) [IrelandRosen1990].
Historical corollary D.108: Several coprime moduli
Let \(N_1,\ldots,N_s\) be pairwise coprime and put
For compatible addresses \(r_j\),
where \(r\) is the unique combined address modulo \(N\).
Proof
Iterate Historical theorem D.107.
Historical standard fact D.109: Finite local reconstruction
Let
be the prime power factorization of a positive integer. The map
is a ring isomorphism. Thus a compatible collection of prime power residues reconstructs one residue modulo \(N\) [IrelandRosen1990].
Historical proposition D.110: Dyadic and odd residue refinement
Let \(N=2^am\) with \(m\) odd. Every residue packet modulo \(N\) factors uniquely as the product of one dyadic packet modulo \(2^a\) and one odd packet modulo \(m\).
Proof
The moduli \(2^a\) and \(m\) are coprime. Apply Historical theorem D.107.
Historical remark D.111
The residue address factors exactly, but valuation weights do not become identical across primes. The odd coordinate system of Subsection D.5 and the dyadic coordinate system of Subsection D.5 remain genuinely different integral charts.