Yes, that was exactly what I couldn't get. Thank you for clarifying it for me!

In summary, the conversation discusses the proof for finding solutions to a system of congruences with relatively prime integers. The proof involves using the Euclidean algorithm and the concept of modular arithmetic. The conversation also touches upon constructing an isomorphism between two groups and the role of Euler's totient function in proving equal cardinality. The summary ends with a clarification on how the statement "Then rm=1 mod n and sn = 1 mod m." is true.
  • #1
Daveyboy
58
0
Hi,

I can not see how this is implied...

Let m and n be positive integers, with gcd(m, n) = 1. The the system of congruences

x = a (mod m) and x = b (mod n ) has a solution. Moreover, any two solutions are congruent modulo mn.

pf.

Since gcd(m,n) = 1, there exist integers r and s such that rm + sn = 1. Then rm=1 mod n and sn = 1 mod m. And the proof goes on.

I just do not understand how "Then rm=1 mod n and sn = 1 mod m." is true.

Can anyone clarify. Thanks
 
Physics news on Phys.org
  • #2
Daveyboy said:
I just do not understand how "Then rm=1 mod n and sn = 1 mod m." is true.
Well, the previous step in the proof was to get the equation
rm + sn = 1,​
(and some of those variables didn't appear beforehand) so I bet that's important...
 
  • #3
... I'm not sure what your getting at but I think your question is why is

rm + sn = 1

true

and it follows from the Euclidean algorithm, which I understand.
 
Last edited:
  • #4
Well, what do you know about modular arithmetic?
 
  • #5
I have some exposure to modular arithmetic, I should know this and understand it clearly but, I have been struggling with it for a while now.

I understand that if x = a (mod n) and x = b (mod m) with gcd(n,m) = 1

they we can find x if we can find integers y and z such that

y = 1 (mod n) and y = 0 (mod m)
and
z = 0 (mod n) and z = 1 (mod m)

with x = you + zb

because

ya + zb = 1a + 0b = a (mod n)
and
ya + zb = 0a + 1b = b (mod m)
 
  • #6
If you have an initial equation rm + sn = 1, and you want to arrive to rm = 1 (mod n), what can you notice in the initial equation regarding divisibility by n?
 
  • #7
here is a less constructive proof. you want to show the map Z--Z/n x Z/m is surjective.

first find the kernel. i.e. which x in Z go to zero in both Z/n and Z/m? such x are divisible by both n and m so are divisible by the product nm (why?).

thus the induced map Z/nm --> Z/n x Z/m is injective since we have set the things that go to zero, themselves equal to zero. but now we have an injective map betwe two sets of the same cardinality, hence it must be surjective.
 
  • #8
Dodo said:
If you have an initial equation rm + sn = 1, and you want to arrive to rm = 1 (mod n), what can you notice in the initial equation regarding divisibility by n?

I notice that n|sn --> sn is congruent to 0 mod n
and rm is congruent to 1 mod n iff rm = 4n + 3 for q an integer, by the division theorem.

but I still am not really seeing anything from this...

mathwonk said:
here is a less constructive proof. you want to show the map Z--Z/n x Z/m is surjective.

first find the kernel. i.e. which x in Z go to zero in both Z/n and Z/m? such x are divisible by both n and m so are divisible by the product nm (why?).

thus the induced map Z/nm --> Z/n x Z/m is injective since we have set the things that go to zero, themselves equal to zero. but now we have an injective map betwe two sets of the same cardinality, hence it must be surjective.

This is a little too funny, this is almost what I am trying to prove. It is nice because I think I am on the right track, maybe I should take a different approach.

I am trying to show ZmnX is isomorphic to ZmXXZnX given that the gcd(m,n) is 1.

I will post my work soon.
 
Last edited:
  • #9
I want to find an isomorphism between the groups as described above.
So, I want f to be bijective and to also satisfy, for [a]mn, mn elements of ZmnX,

I want to show this --> direction, (doest the other way look easier or clearer)

f([a]mnmn) = f([a]mn)f(mn)

... I really don't know how to construct f, I have no idea how to create a bijection even going the other way

for elements [a]m, n of ZmX and ZnX respectively construct a bijection such that

f([a]mn) = f([a]m)f(n)

but the elements look like [a]mn--->([ab]mn)

I have the ker(f) = {([1]m,[1]n)} or {[1]mn} depending on the way I end up going.

I know that Eulers totient function, phi, gives phi(mn)=phi(m)phi(n). All that really gives is equal cardinality though.

WLOG I can claim m>=n.

So, I think I want,

f: [a]mn to ([a]m,[a]n).

So then we have

f([a]mnmn) = f([a]mn)f(mn)

LHS gives
f([a]mnmn) = f([ab]mn) = ([ab]n,[ab]n)

and the RHS gives
f([a]mn)f(mn) = ([a]m,[a]n)(m,n) = ([ab]n,[ab]n)

So the LHS = RHS and that shows this is a homomorphism,

Now for the bijection, using the ker(f) gives the trivial solution this is injective, and with the totient function give that the cardinality is equal, f must also be surjective.

So, does this look right?
 
  • #10
Daveyboy said:
pf.

Since gcd(m,n) = 1, there exist integers r and s such that rm + sn = 1. Then rm=1 mod n and sn = 1 mod m. And the proof goes on.

I just do not understand how "Then rm=1 mod n and sn = 1 mod m." is true.

Can anyone clarify. Thanks
If I understand well, if is VERY EASY! So easy that it could be even confusing.

Definition say that [tex]a \cong b[/tex] mod [tex] n [/tex] IF and ONLY IF [tex] n [/tex] divides [tex] b-a [/tex]. Is that right?
So if you have
[tex] rm + sn = 1 [/tex]
then you have
[tex]sn - 1 = rm[/tex] and [tex] m [/tex] divides obviously [tex] rm [/tex]. So you get that [tex] m [/tex] divides [tex] sn- 1 [/tex] and this is by definition equivalent to say that [tex] sn \cong 1 [/tex] mod [tex] m [/tex].

The next result is similar. [tex]rm + sn = 1[/tex] means [tex]rm -1 = sn[/tex] so [tex] n [/tex] divides [tex]rm - 1[/tex] and you get
[tex]rm \cong 1[/tex] mod [tex] n [/tex].Was this the thing you couldn't get? Or there is something more?
 
Last edited:
  • #11
Can't understand why the TeX writings don't quite work good so I rewrite everuthing in normal text mode.

Daveyboy said:
pf.

Since gcd(m,n) = 1, there exist integers r and s such that rm + sn = 1. Then rm=1 mod n and sn = 1 mod m. And the proof goes on.

I just do not understand how "Then rm=1 mod n and sn = 1 mod m." is true.

Can anyone clarify. Thanks


If I understand well, if is VERY EASY! So easy that it could be even confusing.

Definition say that a = b mod n IF and ONLY IF n divides b-a. Is that right?
So if you have

rm + sn = 1

then you have

sn - 1 = rm

and m divides obviously rm.

So you get that m divides sn - 1 and this is by definition equivalent to say that

sn = 1 mod m.



The next result is similar.

rm + sn = 1

means

rm -1 = sn

so n divides rm - 1 and you get

rm = 1 mod n.


Was this the thing you couldn't get? Or there is something more?
 

FAQ: Yes, that was exactly what I couldn't get. Thank you for clarifying it for me!

What is the Chinese remainder theorem?

The Chinese remainder theorem is a mathematical theorem that provides a method for solving systems of linear congruences with pairwise relatively prime moduli.

How does the Chinese remainder theorem work?

The Chinese remainder theorem involves finding the unique solution to a system of congruences by using the Chinese remainder theorem formula, which involves finding the inverse of each modulus and using modular arithmetic.

What is the significance of the Chinese remainder theorem?

The Chinese remainder theorem has many applications in number theory, cryptography, and computer science. It allows for efficient computation of large numbers and is used in various algorithms and protocols.

What are the limitations of the Chinese remainder theorem?

The Chinese remainder theorem can only be used for systems of congruences with pairwise relatively prime moduli. It also requires the moduli to be coprime with each other, which can be difficult to ensure in some cases.

Are there any real-world applications of the Chinese remainder theorem?

Yes, the Chinese remainder theorem has applications in cryptography, including RSA encryption and decryption. It is also used in error-correcting codes and in finding roots of polynomials over finite fields.

Similar threads

Replies
2
Views
1K
Replies
5
Views
2K
Replies
5
Views
2K
Replies
4
Views
3K
Replies
11
Views
1K
Replies
18
Views
3K
Back
Top