# Recovering a number from a remainder list

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.)

-
Look up the Chinese remainder theorem. –  Ｊ. Ｍ. May 8 '12 at 14:54
If you are learning from a book, surely they will discuss the CRT within a few pages of introducing such equivalences... –  The Chaz 2.0 May 8 '12 at 14:55
Having just read the Wikipedia article on the Chinese remainder theorem, I suddenly feel very, very sorry I asked... For some reason, I mistakenly thought this would be easy. How foolish! –  MathematicalOrchid May 8 '12 at 15:09
@MathematicalOrchid: Your idea is a very good one, and like many good ideas, it has been already found, and there are many implementations. It is convenient to use primes, and in the binary world of computers primes $P_i$ of the form $2^p-1$ are particularly convenient. As I pointed out, numbers are not uniquely picked out, but if the product of our $P_i$ is large enough, that doesn't matter. The important thing is that addition, multiplication can be carried out in parallel mod the $P_i$, and we can use CRT at the end to piece things together. Am impressed that you thought of it. –  André Nicolas May 8 '12 at 15:49
This system has a name: en.wikipedia.org/wiki/Residue_number_system –  Hurkyl May 8 '12 at 19:34

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.$$

-

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.

-

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.

-
If two integers share every single residue, their difference is divisible by every nonzero integer and therefore zero; they are identical. Therefore the set of all residues does uniquely determine an integer. The very same argument can be applied to any infinite set of moduli instead of $\Bbb N$ if desired. –  anon May 8 '12 at 17:49
Indeed the map $\mathbb{Z} \to \hat{\mathbb{Z}}$ is injective. But my point is, that a list of residues need not come from an integer (but if it does, then it is uniquely determined). –  jmc May 8 '12 at 17:55
You say "need not come from an integer" in your comment, but your actual answer says "need not determine an integer." Perhaps you want to put the adjective "profinite" in front of integer in your first sentence. Including this keyword will also help readers unfamiliar with what $\widehat{\Bbb Z}$ means. –  anon May 8 '12 at 18:05
Also, wouldn't the residue of an element $x\in\widehat{\Bbb Z}$ be the images of $x$ under the canonical projection maps, and knowing these is equivalent to knowing $x$? –  anon May 8 '12 at 18:15
The $p$-adic numbers are a bizarre and confusing topic. Still, that's what you get for daring to mention Number Theory. ;-) –  MathematicalOrchid May 8 '12 at 18:45