Inverse chinese remainder theorem

Click For Summary

Discussion Overview

The discussion revolves around finding a method to prove that a number is not a solution to a set of congruences, potentially utilizing the Chinese Remainder Theorem. Participants explore various approaches, including direct substitution and mathematical conditions involving greatest common divisors (gcd) or least common multiples (LCM).

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests that simply plugging a number into the congruences is a straightforward method to check if it is a solution.
  • Another participant proposes looking for a mathematical condition involving gcd or LCM to determine non-solutions, indicating a belief that such a method exists but lacks proof.
  • A counterpoint is raised that plugging in numbers may be inefficient for large numbers or many congruences, advocating for a more analytical approach.
  • One participant describes a method of precomputing information about the system of congruences to facilitate quicker checks in the future.
  • A participant provides an example of a system of congruences and discusses how to derive a specific solution, but another participant challenges the sufficiency of this method by providing a counterexample.
  • Further suggestions include using divisibility tests or creating an array to track solutions for integers against the moduli.
  • A later post reiterates the uniqueness of solutions under the Chinese Remainder Theorem, providing a proof but also noting exceptions in cases where moduli share common factors.

Areas of Agreement / Disagreement

Participants express differing views on the effectiveness of various methods for proving non-solutions to congruences. There is no consensus on a singular approach, and the discussion remains unresolved regarding the best method.

Contextual Notes

Some methods discussed may depend on the specific properties of the moduli involved, such as their common factors, which could affect the applicability of the Chinese Remainder Theorem.

juan avellaneda
Messages
37
Reaction score
0
hi all I am new on the forum

I wonder if is possible to find a method that proofs that a number IS NOT a solution of a set of congruences
Maybe using the chinese remainder theorem??

best regards
japam
 
Physics news on Phys.org
Well, simply plugging in the number in the congruences and seeing it they become true should work, right?
 
method

thats a solution

but i was thinking in other possibility, a mathematical condition
involving the gcd or MCM, for example

im sure that it exists but i don't know how to probe that
 
I can't imagine any way that could be simpler than plugging your number into the equation.

Is there something unusual about your problem that this is not a desirable technique?
 
method

this method is disadvantageous when you have a big number , or a big number of congruences to check

And suppose we want to know all the numbers that don't fit anyone of a set of congruences

In this case, clearly we need a more analytical method
 
this method is disadvantageous when you have a big number , or a big number of congruences to check

I don't see why.



Anyways, it seems that what you really want to do is to spend a lot of time precomputing information about a system of congruences so that, in the future, you can tell quickly if a number satisfies the system.

The easiest way I can imagine to do this is to simply solve the system of congruences, and then your test is simply comparing a given number to the solution.

e.g. if the system was

3x = 4 (mod 5)
x = 7 (mod 11)

The solution is

x = 18 (mod 55)


So for any given integer n, you simply check if n = 18 (mod 55).
 
counterexample

No, i think is wrong

for example

X = 2 (mod 3)

X = 3 (mod 5)

the answer is X = 8 (mod 15)

Now i check the num 11 that doesn't fit the last congruence
but 11 fits the first

so its not a sufficient proof
 
Hurkyl,

This math is new to me. How do you obtain x = 18 (mod 55)?
 
Ok, so you want integers that satisfy none of the congruences.

Again, I cannot divine a better method than simply plugging the integer into each of the congruences.

You could achieve some speed-up, possibly, by computing a divisibility test for each of your moduli. Or, better yet, make a giant array whose length is equal to the LCM of all the moduli, and store "true" and "false" for each entry.


Loren: The problem is small enough that I did it by trial and error. :smile: In general, you can use the Chinese Remainder theorem.
 
  • #10
There is a unique answer.

juan avellaneda said:
hi all I am new on the forum

I wonder if is possible to find a method that proofs that a number IS NOT a solution of a set of congruences
Maybe using the chinese remainder theorem??

best regards
japam

According to the Chinese Remainder Theorem if we have moduli X,Y,Z...which have no common factor, then a specific congruent solution is unique up to multiples of XYZ...

Proof: Let us suppose that W == r, Mod X, W==m Mod Y, W == s Mod Z...etc. And some other number T also satisifies the same set of congruences. If W is not T, consider W-T = A. If we look at the set of congruences we find: W-T = A == 0 Mod X, Y, Z...since W and T have the same residues in that system.

So we find that A is divisible by X, Y, Z, etc...and so A ==0 Mod XYZ...

This means A = KXYZ..., where K is an integer. Thus a solution to the Chinese Remainder problem is unique up to the product of the relatively prime moduli.

PS It might be added that uiqueness would not work in the following situation:

X==0 Mod 2, X==2 Mod 8, X==10 Mod 16. Thus X = 10 works in all three cases, but the product of the modulli is 256, while X=26 also works!
 
Last edited:

Similar threads

MHB Understanding the Chinese Remainder Theorem for $\mathbb{Z}^{\times} _{20}$
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Use of induction in the proof of the Chinese Remainder Theorem
  • · Replies 7 ·
Replies
7
Views
3K
Graduate Generalization of Chinese Remainder Theorem
  • · Replies 1 ·
Replies
1
Views
4K
Why Does Expanding (13-8)^99 Not Yield the Same Remainder as 5^99 Modulo 13?
  • · Replies 7 ·
Replies
7
Views
2K
Graduate Chinese Remainder Theorem, Solving For Multiplicative Inverses
  • · Replies 2 ·
Replies
2
Views
6K
MHB Remainder/factor theorem question
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad ##(p^k -1) \equiv X \mbox{(mod p)}## via Wilson's theorem
  • · Replies 2 ·
Replies
2
Views
1K
Graduate The Chinese Remainder Theorem for moduli that aren't relatively prime
  • · Replies 2 ·
Replies
2
Views
4K
Graduate Is the Proof in Dummit and Foote's Chinese Remainder Theorem Inductive?
  • · Replies 1 ·
Replies
1
Views
4K
Graduate How do I use Chinese remainder theorem to solve for x mod 683 in Cryptography?
  • · Replies 12 ·
Replies
12
Views
4K