Is there a way to calculate $a \operatorname{mod} cd$, without actually calculating $cd$, where $c$ and $d$ are primes, and $cd$ has $12$ digits?
Asked
Active
Viewed 37 times
0
-
3Maybe Chinese Remainder Theorem is what you're looking for? It allows you to calculate $a\bmod (cd)$ if you know $a\bmod c$ and $a\bmod d$. – Peter Košinár Aug 25 '13 at 08:56
1 Answers
1
Yes.
If we denote $a \equiv a_c \pmod c$ and $a \equiv a_d \pmod d$, we compute $c^{-1} \pmod d$ and $d^{-1} \pmod c$ using perhaps the Extended Euclidean Algorithm, then
$$a \equiv a_c d^{-1} d + a_d c^{-1} c \pmod {cd},$$
where by $c^{-1}$ and $d^{-1}$, I mean the integers calculated above by a slight abuse of notation. This is what would come from a constructive proof of the Chinese Remainder Theorem (as is highlighted in a blog post I wrote for my students, self-plug disclaimer).
davidlowryduda
- 91,687