1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks! Yeah, that makes sense that one can't get $x\bmod{N-1}$ from $x\bmod{N}$. But what if one allows additional information? It's not clear to me that only residues mod factors of $N-1$ will help. $\endgroup$ Oct 2 '15 at 21:13
  • $\begingroup$ Thanks for the update! Consider this though: 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 simply not true that the $q$'s need to be factors of $N-1$ to reveal more information about $x$. (I'm considering $x$ as an integer, and not a residue class.) $\endgroup$ Oct 2 '15 at 22:13
  • $\begingroup$ @ArmadilloJim - I deleted my previous comment and transferred the point, in much more detail (and hopefully more clarity!) to the body of the answer. The summary is that if all your $q$'s are relatively prime with $N-1$, then (a) they tell you nothing about $x$ mod $N-1$ unless you also have a bound on the size of $x$, and (b) if you do have such a bound, then any sequence of $q$'s will eventually allow you to determine $x$ completely, and you will not know its residue mod $N-1$ until you actually know it completely. $\endgroup$ Oct 3 '15 at 16:29
  • 1
    $\begingroup$ Thanks again for your answer! I understand what you're saying offers a good reason not to be hopeful, but I s'pose I still don't understand how this is a proof that no clever algorithm exists. I need to thinker on it some more. You've been very helpful! $\endgroup$ Oct 4 '15 at 0:54
  • $\begingroup$ @ArmadilloJim - do you see why, if the only info you have about $x$ is its residue mod the $p$'s and mod $q$ for various $q$'s that are relatively prime with $N-1$, the CRT implies that $x$ could have any residue mod $N-1$? $\endgroup$ Oct 5 '15 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.