Inverse chinese remainder theorem

• Feb 27, 2004

• #1

juan avellaneda

37

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

• Physicists measure quantum geometry for first time
• Scientists observe 'negative time' in quantum experiments
• Researchers take 'significant leap forward' with quantum simulation of molecular electron transfer

• Feb 27, 2004

• #2

Muzza

695

1

Well, simply plugging in the number in the congruences and seeing it they become true should work, right?

 

• Feb 27, 2004

• #3

juan avellaneda

37

0

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

 

• Feb 27, 2004

• #4

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

14,983

28

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?

 

• Feb 27, 2004

• #5

juan avellaneda

37

0

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

 

• Feb 27, 2004

• #6

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

14,983

28

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

 

• Feb 27, 2004

• #7

juan avellaneda

37

0

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

 

• Feb 27, 2004

• #8

Loren Booda

3,125

4

Hurkyl,

This math is new to me. How do you obtain x = 18 (mod 55)?

 

• Feb 27, 2004

• #9

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

14,983

28

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. In general, you can use the Chinese Remainder theorem.

 

• Jul 6, 2004

• #10

robert Ihnot

1,059

1

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: Jul 6, 2004

FAQ: Inverse chinese remainder theorem

What is the Inverse Chinese Remainder Theorem?

The Inverse Chinese Remainder Theorem is a mathematical theorem that states that if a system of linear congruences have pairwise relatively prime moduli, then there exists a unique solution to the system of congruences.

How is the Inverse Chinese Remainder Theorem used in cryptography?

The Inverse Chinese Remainder Theorem is used in cryptography to solve systems of congruences in the decryption process. It allows for the efficient decoding of encrypted messages by breaking them into smaller parts and then combining them using the theorem.

What are the prerequisites for understanding the Inverse Chinese Remainder Theorem?

A strong understanding of modular arithmetic and linear congruences is necessary to fully grasp the Inverse Chinese Remainder Theorem. Knowledge of number theory and abstract algebra is also helpful.

Can the Inverse Chinese Remainder Theorem be applied to non-linear systems?

No, the Inverse Chinese Remainder Theorem only applies to systems of linear congruences. If the system is non-linear, then it cannot be solved using this theorem.

Is the Inverse Chinese Remainder Theorem a generalization of the Chinese Remainder Theorem?

Yes, the Inverse Chinese Remainder Theorem is a generalization of the Chinese Remainder Theorem. It extends the concept to systems with non-coprime moduli, which was not possible with the original theorem.