Is there something like the Chinese remainder theorem for $N-1 = \Pi p_i - 1$?

220 Views Asked by At

S'pose I know that $x\equiv a_i \bmod{p_i}$ where the $p_i$'s are prime. The Chinese remainder theorem allows me to reconstruct $x$ modulo $N=\Pi p_i$.

In general, is it possible to also reconstruct $x$ modulo $N-1$? The answer is "no", right?

What if I have additional information? Specifically, s'pose I don't know how to factorize $N-1$, but I do know the remainders of $x$ with additional moduli. Say, $x\equiv b_i \bmod{q_i}$ where the set of $q_i$'s is disjoint from the set of $p_i$'s.

Alternatively, what if I knew the residues of $x$ mod $p_i^2$ for all $i$? That is, shifting from $x\bmod{N}$ to $x\bmod{N-1}$ requires knowing something about the quotient (and not just the remainder). What of $x$ mod $p_i^k$ for all $i,k$, an expansion of $x$ in base $p_i$?

I've been banging my head against this for a while so if I'm missing something really obvious, feel free to leave a hint rather than a complete answer. I'm feeling rather dense.

EDIT: A somewhat-useless but true statement is that there is an infinitude of primes so one can always find a $q$ larger than $x$. Then knowing $x\bmod{q}$ gives $x$, and a direct computation of $x\bmod{N-1}$ is possible. Thus it's not true that the $q$'s need to be factors of $N-1$ to reveal more information about $x$. At the same time, I wonder if there's a more clever, less extreme example than this tautological-like one.

1

There are 1 best solutions below

7
On BEST ANSWER

You cannot know $x$ mod $N-1$ unless your $q$'s are the prime power factors of $N-1$ (or any list of pairwise relatively prime numbers with product $N-1$). This is actually a consequence of the Chinese Remainder Theorem. Here's what I mean:

The CRT says that for any pairwise relatively prime $A_1$, $A_2$, etc., you can arbitrarily pick residues $a_1$ for $A_1$, $a_2$ for $A_2$, and there will be an $x$ that is $\equiv a_1$ mod $A_1$ and $\equiv a_2$ mod $A_2$, etc. (And it will be determined uniquely mod $A_1A_2...$ etc. but put that aside for a moment.) If you meditate on the fact that this statement works for any choice of $a_1$ mod $A_1$ and any choice of $a_2$ mod $A_2$ etc., you will realize that it is telling you that information about a number's residue mod $A_1$ tells you nothing about its residue mod $A_2$, and vice versa!

In your situation, $N$ and $N-1$ are relatively prime. This means a number's residue mod $N$ and mod $N-1$ are essentially unrelated to each other. (I.e. there exist numbers realizing every possible pair of residues mod $N$ and mod $N-1$.)

Furthermore, and by the same token, if you know something about $x$ mod $q$, this tells you nothing about $x$ mod $N-1$ if $q$ and $N-1$ are relatively prime. On the other hand, if $q$ shares a factor with $N-1$, then you will at least know $x$ mod this common factor. For example, suppose $N=210=2\cdot 3\cdot 5\cdot 7$, so $N-1 = 209 = 11\cdot 19$, suppose $q=190$, and suppose that we know $x = 17$ mod $q$. Well, $q$ and $N-1$ share the common factor $19$. So $x=17$ mod $q$ also tells us $x=17$ mod $19$, and this tells us that $x$ mod $N-1$ will be something that is 17 mod 19, so it could be that $x$ is any of 17, 36, 55, 74, ..., 207 mod $N-1$.

So your $q$'s will give you info about $x$ mod $N-1$ exactly to the extent that they share factors with $N-1$. If your $q$'s are pairwise relatively prime with product $N-1$, then again by the CRT they will let you reconstruct $x$ mod $N-1$ completely.

ADDENDUM: Regarding your "alternatively" edit. If you know $x$'s residue mod $p^k$ for all $k$, for even a single $p$, this in principle is enough to pin down $x$ (not just mod $N-1$ but completely), because every pair of numbers that are different at all will differ mod $p^k$ for sufficiently high $k$ (e.g. high enough so that $p^k$ is higher than both of them).

Depending on your needs this may be hard to use in practice. No finite number of $p^k$'s will be enough information, for the same reasons discussed in this answer, unless you have some additional information such as a bound on the size of $x$.

ADDENDUM II: Regarding your "EDIT" edit. This point hinges on what information you have about $x$. Specifically, do you have a bound on its size? Without a bound on $x$'s size, then even if $q$ is bigger than $x$, finding out $x$ mod $q$ doesn't tell you $x$ because you don't know $q$ is bigger than $x$. To make the point concrete, if I tell you $x$ is 1,343 mod $22,851$, because actually I secretly know $x$ is 1,343, then you don't whether $x$ is $1,343$, $1,343 + 22,851$, $1,343 + 2\cdot 22,851$, etc. unless you also know $x$ is smaller than something.

The way I have been interpreting your question is captured by the following scenario. Let me know if I'm misinterpreting it: I think of a secret natural number $x$, and tell you its residue mod $p_i$ for a finite list of primes $p_1,\dots,p_n$ that you specify. You then deduce its residue mod $N=\prod p_i$. Now you play sort of a 20-questions game with me where you can ask me questions like "what is its residue mod $q$?" or "what is its residue mod $p_i^k$?" and I answer. You win if you can correctly deduce its residue mod $N-1$. What information do you need to ask for in order to win?

If this is really the setup, then the answer written above stands. You can deduce $x$'s residue mod $N-1$ if and only if you ask for its residue mod $q$ for a list of $q$'s such that their gcd's with $N-1$ (contain a list of numbers that) are pairwise relatively prime and have product $N-1$. Then you can use the CRT to deduce $x$'s residue mod $N-1$. If you ask about a finite list of $q$'s that do not share factors with $N-1$, you learn literally nothing about $x$ mod $N-1$. This follows from the CRT as discussed above.

On the other hand, if you are also allowed to ask me for an overall bound on $x$'s size, then (a) you should! and (b) once you have a bound on $x$'s size, then actually any sequence of queries asking for $x$ mod various new things will eventually pin down $x$ not just mod $N-1$ but completely. In fact, as soon as the lcm of all the moduli you have queried exceeds the bound on $x$, you can pin down $x$: if you know $x$ mod some list of moduli $q_i$ (including the $p_i$), then the CRT lets you determine $x$'s residue mod the lcm of the $q_i$ (call it $M$). If you also know $x$ is less than $M$, then at this point you know it exactly.

Likewise, if you can simultaneously ask me for $x$'s residue mod $p^k$ for all $k$ (even just for a single prime $p$), and if you can somehow process this infinite amount of information, then this also pins down $x$ not just mod $N-1$ but exactly, as discussed in the previous addendum.

I imagine you might be interested in the question of if, in any of these scenarios, it is possible to determine $x$ mod $N-1$ prior to determining it exactly, i.e. could you have enough info that you could be sure of $x$'s residue mod $N-1$ but still unsure of $x$'s actual value.

As above, this will certainly be true if your queries share enough factors with $N-1$. However, if your queries are all relatively prime to $N-1$, I think it will be impossible to know $x$ mod $N-1$ unless you actually know it completely. For example, if $p\nmid N-1$, then knowing $x$ mod $p^k$ for any finite $k$ tells you nothing about $x$ mod $N-1$, as above, by the CRT. If you can simultaneously process the info of $x$ mod $p^k$ for all $k$ then that actually tells you $x$'s true value. There's no in-between. Likewise, if you know a bound $K$ on $x$'s size, then meanwhile, your queries pin down $x$ mod their lcm $M$, which grows with each new query, so you only have a finite list of possibilities for $x$: if $x$'s residue class mod $M$ is represented by a natural number $\bar x < M$, then the possibilities are $\bar x, \bar x + M, \bar x + 2M,\dots$ until you exceed $K$. (So as soon as you ask enough questions that $M > K$, you know $x$ exactly, as discussed above; in fact, you're done as soon as $\bar x + M > K$.) But if $M$ is relatively prime with $N-1$ (because your queries didn't share factors with $N-1$), then these possibilities will all be different mod $N-1$ (they will not start repeating until they have hit every possibility mod $N-1$). So you won't have a single possibility mod $N-1$ unless you actually have pinned down $x$ to just one possibility period.

Aside for interested readers: This question and answer are related to the strong approximation theorem, applied to the field of rational numbers. Suppose $x$ is rational. The statement that $x$ is an integer tells us that $v_p(x)\geq 0$ for every prime $p$ (i.e. for every finite place of $\mathbb{Q}$), and thus $x$'s image in each $p$-adic completion of $\mathbb{Q}$ is restricted to a unit ball. If we further know $x$ mod various primes $p_i$, then we know $x$'s image is restricted to smaller balls in each of the corresponding completions, and if we even know $x$ mod $p^k$ for some finite $p^k$'s, then $x$'s image is restricted to even smaller balls. Thus $x$ is contained in a compact subset of the restricted product $\prod_p' \mathbb{Q}_p$. However if we know nothing about $x$'s size (i.e. we have no info about its image in $\mathbb{R}$, the completion of $\mathbb{Q}$ at the infinite place), then $x$ could still be anywhere in that compact subset: strong approximation tells us that the image of $\mathbb{Q}$ in the restricted product $\prod_p'\mathbb{Q}_p$ is dense! On the other hand, if we additionally have information about $x$'s size, then it is also contained in a ball in the last completion $\mathbb{R}$, which means we know $x$ is in a compact subset in the full adele ring $\mathbb{A}_\mathbb{Q}$. Since the image of $\mathbb{Q}$ in $\mathbb{A}_\mathbb{Q}$ is discrete, this means there are only a finite set of possibilities for $x$, and making the balls smaller by finding out $x$ mod $q$ for more $q$, or mod $p^k$ for higher $k$, will eventually pin it down to just one.