3
$\begingroup$

Consider the following list of equations:

$\begin{align*} x \bmod 2 &= 1\\ x \bmod 3 &= 1\\ x \bmod 5 &= 3 \end{align*}$

How many equations like this do you need to write in order to uniquely determine $x$?

Once you have the necessary number of equations, how would you actually determine $x$?


Update:

The "usual" way to describe a number $x$ is by writing

$x = \sum_n 10^n \cdot a_n$

and listing the $a_n$ values that aren't zero. (You can also extend this to some radix other than 10.)

What I'm interested in is whether you could instead express a number by listing all its residues against a suitable set of modulii. (And I'm guessing that the prime numbers would constitute such a "suitable set".)

If you were to do this, how many terms would you need to quote before a third party would be able to tell which number you're trying to describe?

That was my question. However, since it appears that the Chinese remainder theorem is extremely hard, I guess this is a bad way to denote numbers...

(It also appears that $x$ will never be uniquely determined without an upper bound.)

  • 0
    @André +1 For emphasizing the opportunity for *parallelization* - which may prove crucial in both theory and practice.2012-05-08

3 Answers 3

0

Note that even if you specify the residue of $x$ modulo all integers $n$, this need not determine an integer.

This is where $\hat{\mathbb{Z}}$ comes into the picture. I think you should know this as a fact, just to be complete (no pun intended). But I warn you that the theory going into $\hat{\mathbb{Z}}$ is much more advanced than CRT.

If you do want to know more about this, look into http://en.wikipedia.org/wiki/P-adic_number . Especially the part on $p$-adic expansion is interesting, because it is analogous in some sense to writing integers in radix 10.

Probably the greatest difference is that the sum in the expansion need not be a finite sum.

  • 0
    Also, at any rate, welcome to MSE! Hope you enjoy. :) (And if a message pops up about extended discussion and moving to chat just ignore it.)2012-05-09
4

Hint $ $ It can be done simply without CRT. $\rm\:x\equiv -2\:\ (mod\ \rm3,5)\iff x\equiv -2\equiv 13\pmod{ 15}\:$ Now since $13\equiv 1\pmod 2\:$ we conclude $\rm\:x\equiv 13\:\ (mod\ 2,15)\iff x\equiv 13\pmod{30}\:$

Hence your hunch was correct: it is easy (these are often warm-up exercises to CRT).

Thus this constant case of CRT is solved simply by taking least common multiple of moduli:

$\rm x\equiv a\ (mod\ m,n)\!\iff\! m,n\:|\:x\!-\!a\!\iff\! lcm(m,n)\:|\:x\!-\!a\!\iff\! x\equiv a\ (mod\: lcm(m,n)) $

This simple constant-case optimization of CRT arises quite frequently in practice, esp. for small moduli (by the law of small numbers), so it is well worth checking for. For further examples, see here where it simplified a few page calculation to a few lines, and here and here.

Note that I chose to eliminate the largest moduli first, i.e. $\rm\:x\equiv -2\ mod\ 3,5\:$ vs. $\rm\:x\equiv 1\ mod\ 2,3\:$ since that leaves the remaining modulus minimal ($= 2 $ vs. $5$ above), which generally simplifies matters if we need to apply the full CRT algorithm in the final step (luckily we did not above).

Update $ $ Regarding your update: knowing the residues of $\rm\:n\:$ modulo a finite set $\rm\:S\:$ of moduli only determines $\rm\:n\:$ modulo $\rm\:lcm\:S.\:$ However, if $\rm\:S\:$ is infinite (e.g. all primes), then the residues do determine $\rm\:n\:$ uniquely from the residue of any modulus $\rm > n$.

In cases where one is working with bounded size integers such modular representations can prove effective for computational purposes, esp. if the moduli are chosen related to machine word size, so to simplify arithmetic. See any good textbook on computer algebra, which will discuss not only this but many other instances of modular reduction - a ubiquitous technique in algebraic computation.

2

This is a classic example of Chinese remainder theorem. To solve it, one typically proceeds as follows. We have $x = 2k_2 + 1 = 3k_3 + 1 = 5k_5 + 3.$ Since $\displaystyle x = 2k_2 + 1 = 3k_3 + 1$, we have that $2k_2 = 3k_3$ i.e. $2|k_3$ and $3|k_2$, since $(2,3) = 1$. Hence, $k_3 = 2k_6$ and $k_2 = 2k_6$. Hence, we now get that $x = 6k_6 + 1 = 5k_5+3.$ Rearranging, we get that $6k_6 - 5k_5 = 2.$ Clearly, $(2,2)$ is a solution to the above. In general, if $ax+by$ has integer solutions and $(x_0,y_0)$ is one such integer solution, then all integer solutions are given by $(x,y) = \displaystyle \left( x_0 + k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{a}, y_0 - k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{b} \right)$ where $k \in \mathbb{Z}$. Hence, all the integer solutions to $6k_6 - 5k_5 = 2$, are given by $(k_6,k_5) = \left( 2 + 5k, 2 + 6k \right)$ Hence, $x = 5k_5 + 3 = 30k + 13$ i.e. $x \equiv 13 \bmod 30.$