Chinese Remainder Theorem, Solving For Multiplicative Inverses

In summary, the conversation discusses solving sets of linear congruence with the Chinese remainder theorem, specifically when the a term is larger than the modulo m. It also touches on solving for inverses and finding the least possible value of N in a system of linear congruences. The conversation provides a hint using the equation 77x = 1 (mod 3) and suggests looking for a recursive method to find N.
  • #1
cwatki14
57
0
So I am working on solving sets of linear congruence with the chinese remainder theorem. When I go to solve for the inverses I am meeting a bit of trouble. What do I do when the a term is larger that m?
Example
77x=1(mod3)
33y=1(mod7)
21z=1(mod11)
where x,y,z are the inverses I am trying to solve for so I can use the chinese remainder thm. I usually solve for congruences by applying the euclidean algorithm backwards, but I have never encountered the situation where the a term is larger than the modulo m... What do I do to solve for these inverses?

Also, I am looking at a system of linear congruences like the following
N=0(mod[tex]\phi[/tex]1)
N=-1(mod[tex]\phi[/tex]2)
...
N=-(n-1)(mod[tex]\phi[/tex]n)
A unique solution exists since ([tex]\phi[/tex]n,[tex]\phi[/tex]m)=1 whenever m does not equal n.
So it asks when n=2 what is the least possible value of N? How do I do this/ solve for the inverses? I didn't think it was referring to phi of n or phi of m more like phi sub n or phi sub m, but I am not entirely sure...
 
Physics news on Phys.org
  • #2
A hint for your first question:

If a = b (mod m), then ax = bx (mod m).

Find a way to apply this to, say, the equation 77x = 1 (mod 3).

HTH

Petek
 
  • #3
cwatki14 said:
So I am working on solving sets of linear congruence with the chinese remainder theorem. When I go to solve for the inverses I am meeting a bit of trouble. What do I do when the a term is larger that m?
Example
77x=1(mod3)
33y=1(mod7)
21z=1(mod11)
where x,y,z are the inverses I am trying to solve for so I can use the chinese remainder thm. I usually solve for congruences by applying the euclidean algorithm backwards, but I have never encountered the situation where the a term is larger than the modulo m... What do I do to solve for these inverses?

Also, I am looking at a system of linear congruences like the following
N=0(mod[tex]\phi[/tex]1)
N=-1(mod[tex]\phi[/tex]2)
...
N=-(n-1)(mod[tex]\phi[/tex]n)
A unique solution exists since ([tex]\phi[/tex]n,[tex]\phi[/tex]m)=1 whenever m does not equal n.
So it asks when n=2 what is the least possible value of N? How do I do this/ solve for the inverses? I didn't think it was referringw to phi of n or phi of m more like phi sub n or phi sub m, but I am not entirely sure...
the answer to the first part is that you can always subtract 0 mod m from both sides. Therefore since 75x = 0 mod 3, 77x-75x =1-0 mod 3. the answer to the second part is to look for a recursive method to find N then see if that can be reduced to a direct formula as a function of n . The simple answer to the second part is different depending upon whether N is an negative or positive number. Assuming N is positive and n = 5 the second smallest number N would be 61.
 
Last edited:

1. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that allows for the simultaneous solution of a system of linear congruences. In simpler terms, it helps find the unique solution to a system of equations with different moduli.

2. How does the Chinese Remainder Theorem work?

The Chinese Remainder Theorem works by finding the smallest positive integer that satisfies all of the given congruences. This is done by using the Chinese Remainder Theorem algorithm, which involves finding the multiplicatives inverses of the given numbers and using them to combine the congruences.

3. What is a multiplicative inverse?

A multiplicative inverse, also known as a reciprocal, is a number that when multiplied by another number results in a product of 1. In modular arithmetic, the multiplicative inverse of a number is the number that, when multiplied by the original number, results in a remainder of 1 when divided by a given modulus.

4. How is the Chinese Remainder Theorem used in cryptography?

The Chinese Remainder Theorem is used in cryptography as a way to efficiently encrypt and decrypt messages. It allows for the use of smaller moduli, making the encryption process faster and more secure. It is also used in the RSA algorithm, which is commonly used in modern cryptography.

5. What are the benefits of using the Chinese Remainder Theorem?

The Chinese Remainder Theorem has several benefits, including its ability to efficiently solve systems of congruences, its use in cryptography, and its application in solving real-world problems such as scheduling and resource allocation. It also allows for the use of smaller moduli, making calculations faster and more efficient.

Similar threads

Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
799
  • General Math
Replies
11
Views
3K
  • Linear and Abstract Algebra
Replies
4
Views
725
  • Calculus and Beyond Homework Help
Replies
2
Views
983
Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
12
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
Back
Top