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

[Daveyboy]

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

 

[Hurkyl]

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

 

[Daveyboy]

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

 

[Hurkyl]

Well, what do you know about modular arithmetic?

 

[Daveyboy]

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)

 

[dodo]

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?

 

[mathwonk]

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.

 

[Daveyboy]

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

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 Z_mn^X is isomorphic to Z_m^XXZ_n^X given that the gcd(m,n) is 1.

I will post my work soon.

 

[Daveyboy]

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 Z_mn^X,

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 Z_m^X and Z_n^X 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?

 

[Take_it_Easy]

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 \cong 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 \cong 1$$ mod $$m$$.

The next result is similar. $$rm + sn = 1$$ means $$rm -1 = sn$$ so $$n$$ divides $$rm - 1$$ and you get
$$rm \cong 1$$ mod $$n$$.Was this the thing you couldn't get? Or there is something more?

 

[Take_it_Easy]

Can't understand why the TeX writings don't quite work good so I rewrite everuthing in normal text mode.

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?