Question

looking for a simple proof
show that

\[\left.\begin{array}{} a\equiv b\pmod{m}\\a\equiv b\pmod{n}
\end{array}\right\}\implies a\equiv b \pmod{\rm{lcm}(m,n)}\]

\(m,n,a,b \in \mathbb{Z}\)

Answer 1

i guess this is equivalent to proving
\(m|c \) and \(n|c\) \(\implies\) \(\rm{lcm}(m, n) | c\)

where \(c = a-b\)

Answer 2

I agree the first part, but second I'm not so sure. Seems like you should be able to use chinese remainder theorem

Answer 3

so we don't know if they are relatively prime
... hmm, if you want I can ask my teacher in a few hours. He LOVES LOVES LOVES number theory

Answer 4

please do fib, im really looking for a short and neat proof xD

Answer 5

will do, he'll love it

Answer 6

idk why, but I feel like this just cannot be true for all numbers

Answer 7

so in words we have, for any m,n where there exists a,b s.t. \(a\equiv bmodm\equiv bmod n\) then \(a\equiv b(mod~lcm(m,n))\)

...

Answer 8

yes they could be any integers
\(m,n,a,b \in \mathbb{Z}\)

Answer 9

il add this to the main question..

Answer 10

could attempt a contrapositive proof, but I doubt that'd be short

Answer 11

\( \begin{array}l\color{red}{\text{o}}\color{orange}{\text{k}}\color{#E6E600}{\text{ }}\color{green}{\text{f}}\color{blue}{\text{r}}\color{purple}{\text{o}}\color{purple}{\text{m}}\color{red}{\text{ }}\color{orange}{\text{b}}\color{#E6E600}{\text{o}}\color{green}{\text{t}}\color{blue}{\text{h}}\color{purple}{\text{ }}\color{purple}{\text{e}}\color{red}{\text{q}}\color{orange}{\text{u}}\color{#E6E600}{\text{a}}\color{green}{\text{t}}\color{blue}{\text{i}}\color{purple}{\text{o}}\color{purple}{\text{n}}\color{red}{\text{ }}\color{orange}{\text{w}}\color{#E6E600}{\text{e}}\color{green}{\text{ }}\color{blue}{\text{g}}\color{purple}{\text{o}}\color{purple}{\text{t}}\color{red}{\text{ }}\color{orange}{\text{♫}}\color{#E6E600}{\text{♬}}\color{green}{\text{}}\end{array} \) \(a=b \mod{(n\times m)}\\ \)

Answer 12

case 1 when gcd(m,n)=1 then lcm(m,n)=m*n/gcd(n,m)=m*n
done

Answer 13

case 2
when gcd(n,m)=d

Answer 14

thats right, when \(m,n\) are coprime it is obvious that
\[m|c~~\text{and}~~n|c \implies mn |c\]

Answer 15

but im looking for a proof, not just intuition

Answer 16

hmm i was proving :| (sill dint finish second part)
what do u mean of proof ?
do u have an idea ?

Answer 17

\[\begin{array}l\color{red}{\text{o}}\color{orange}{\text{k}}\color{#E6E600}{\text{ }}\color{green}{\text{f}}\color{blue}{\text{r}}\color{purple}{\text{o}}\color{purple}{\text{m}}\color{red}{\text{ }}\color{orange}{\text{b}}\color{#E6E600}{\text{o}}\color{green}{\text{t}}\color{blue}{\text{h}}\color{purple}{\text{ }}\color{purple}{\text{e}}\color{red}{\text{q}}\color{orange}{\text{u}}\color{#E6E600}{\text{a}}\color{green}{\text{t}}\color{blue}{\text{i}}\color{purple}{\text{o}}\color{purple}{\text{n}}\color{red}{\text{ }}\color{orange}{\text{w}}\color{#E6E600}{\text{e}}\color{green}{\text{ }}\color{blue}{\text{g}}\color{purple}{\text{o}}\color{purple}{\text{t}}\color{red}{\text{ }}\color{orange}{\text{♫}}\color{#E6E600}{\text{♬}}\color{green}{\text{}}\end{array} a=b \mod{(n\times m)}\\\]

how did u get this ?

Answer 18

did u miss lcm inside mod ?

Answer 19

haha ok i'll rewrite i guess i got what u mean

Answer 20

for any integer number is a set of primes:
a = 2*3*...(for example).
a= w *m. -->1
a= r*n. -->2
we will assume that n> m (if = it is trivial)
h=lcm(m,n) = n*x.
thus a/h=r/x.
and factors of x (I will use letter u for factors ):
-u in m and not in n: Or (u is repeated in m more than n).
\[u \notin n . u \in m \rightarrow u \in r.\]
thus r/x = integer .

Answer 21

Are you the @ganeshie8

Answer 22

there* :P

Answer 23

\(\Large m=gcd(n,m)x \Rightarrow m|a-b \Rightarrow x gcd(n,m)|a-b\\
\Large n=gcd(n,m)y \Rightarrow n|a-b \Rightarrow y gcd(n,m)|a-b \\
\text {there for }\\
\large xy gcd(n,m)|a-b \\\text {but }\\

\Large lcm(n,m)=\frac{m*n}{gcd(n,m)}=\frac{xy(gcd(n,m)^2 )}{gcd(n,m)} =xy gcd(n,m)\\\text {thus }\\
\Large lcm(n,m)|a-b\\
\Large a=b\mod(lcm) \)

Answer 24

that looks more like the one im thinking about, let me see if i get it it correctly

since m|a and n|a, you're writing a = w*m = r*n
next, you're showing that a/gcd(m,n) is an integer. pretty clever xD il still need to go through it multiple times to make sense of it fully

Answer 25

i have another proof hmm
but i likes @catch.me idea

Answer 26

one sec, let me go through you proof @Marki

Answer 27

i dint follow it with
gcd(x,y)=1

Answer 28

@Marki thanks ,but i didn't understand what you wrote!

Answer 29

\(\Large m=\gcd(n,m)x \Rightarrow m|a-b \Rightarrow x \gcd(n,m)|a-b\\
\Large n=\gcd(n,m)y \Rightarrow n|a-b \Rightarrow y \gcd(n,m)|a-b \\
\text {there fore }\\
\large \color{Red}{xy \gcd(n,m)|a-b }\\\\\)




why are we allowed to conclude like this @Marki ?

Answer 30

looks there is some typo

think she meant xy | (a-b)

Answer 31

\(\Large m=\gcd(n,m)x \Rightarrow m|a-b \Rightarrow x|a-b\\
\Large n=\gcd(n,m)y \Rightarrow n|a-b \Rightarrow y|a-b \\
\text {there fore }\\
\large \color{Red}{xy |a-b }\\\\\)

this is true because x and y are relatively prime

Answer 32

\(\Large n=\prod p_i^{k_i}\\\Large m=\prod p_j^{k_j}\\ \Large gcd(n,m)=\prod p_g^{k_g} \)

thus one *unique divisor * of both satisfy that property

Answer 33

see
mn=xy gcd(n,m) ^2
but as the property said one unique divisor ( for m,n means not to pick power of primes )
as gcd(x,y)=1 we pick them both but we had gcd(n,m)^2
we take gcd(n,m) alone hmmm
i'll try to show u in proper words

Answer 34

that looks good to me !

Answer 35

I see.. that works because of the definition of lcm : \[\mathrm{lcm(m,n)} = \prod_{i=1}^r p_i^{\mathrm{max}\{m_i,n_i\}}\]

Answer 36

without loss of generality
\(\Large n=\prod p_i^{k_i}\\m=\prod p_j^{g_j}\\ \Large gcd(n,m)=\prod p_i^{|k_i-q_j|} \\ \Large gcd(gcd(n,m),x,y)=1 \)

Answer 37

yes thats even more neat xD

Answer 38

i have just removed gcd from your proof :)

Answer 39

i saw this proof once but never wrote it again ,i guess it was using max notation as well xD

Answer 40

fixed typo :

consider prime factorization of \(m\) and \(n\) :
\(\large m = p_1^{m_1}p_2^{m_2} \cdots p_r^{m_r}\)

\(\large n = p_1^{n_1}p_2^{n_2} \cdots p_r^{n_r}\)

since \(m|c\) and \(n|c\), we have \(p_i^{\max\{m_i, n_i\}} ~\Big | ~c\) and consequently \(\mathrm{lcm}(m,n) | c\)
\(\blacksquare\)

Answer 41

nice

Answer 42

so, from my teacher, if m and n a relatively prime by chinese remainder, this is obvious. The issue(which he hasn't solved yet) is when they are not relatively prime

Answer 43

we attempted the prime factorization method of reducing but the issue was being rigorous

Answer 44

apply Chinese theorem for the least un common primes

Answer 45

then do some stuff

Answer 46

I do not understand what you mean there

Answer 47

idk lol :P

Answer 48

Ya see, I wanted to do the prime factorization then remove the common primes
but rigorously, was the issue

Answer 49

whats ur question anyway ?

Answer 50

this sentence makes no sense to me "apply Chinese theorem for the least un common primes "

Answer 51

sorry about that xD

Answer 52

which, is my confusion, but anyways, yea, so we need to determine how to break m and n down into their prime factorizations then determine a way to set up chinese remainder

Answer 53

interesting xD yeah chinese remainder thm requires moduli to be relative prime when taken in pairs. rigorous proof without using prime factorization looks very tricky

Answer 54

well, it gives us a two case proof, case 1 they're relatively prime, case2 they're not

Answer 55

im not getting any ideas atm, il wait for your proof fib :)

Answer 56

haha, my teacher didn't get it in the 20 minutes he looked at it. His intuition was to try and use the proof of the chinese remainder thm somehow

Answer 57

If \(a\equiv b\pmod m\) and \(a\equiv b\pmod n\) then below also holds :

\(a\equiv b\pmod{d}\) where \(d\) is any divisor of \(m\) or \(n\)

but this logic is also similar to prime factorization hmm..

Answer 58

well, I was thinking reverse chinese simplification for lcm (m,n) when relatively prime, but I guess generically we can just break it down into their primes, then say on the ones it shares are this way too somehow