Thread: Congruence problem with LCM

Let a,b,f,g,m be integebers with a>b>1>1. If f congruence g (mod a), f congruence g (mod b), and m = lcm(a,b), prove f congruence g (mod m)

Originally Posted by tttcomrader

Let a,b,f,g,m be integebers with a>b>1>1. If f congruence g (mod a), f congruence g (mod b), and m = lcm(a,b), prove f congruence g (mod m)

Given two positive integers: a,b

We can find two positive integers: x,y

Such that: lcm(a,b)=xy and x|a , y|b and gcd(x,y)=1

Now if,
f = g (mod a)
Then it is true from any divisor of "a" let x|a then:
f = g (mod x)
Similarly
f = g (mod y)

Note, gcd(x,y)=1 thus,
f = g (mod xy) thus, f = g (mod m)

Here is a nicer way of saying it.

f = g (mod a)
f = g (mod b)

Let c = f - g.

Then, by definition,
a|c and b|c

And we want to show,
f=g (mod m)
Meaning,
m|c

Theorem
Now we will show that if a,b,c are positive integers.
And a|c and b|c and if d=gcd(a,b) then ab|cd.
(You will see why we show this).

Proof
Since d=gcd(a,b) a powerful theorem says we can find integers x,y such that,
ax+by=d
That means,
cd=c(ax+by)=acx+bcy
Now, it is trivial to see that,
ab|acx and ab|bcy.
Thus,
ab|(acx+bcy) i.e. ab|cd
Q.E.D.

Now the result is immediate.
We can write the fraction (which is an integer) as,
(cd)/(ab)=(c)/(ab/d)
But!
m=lcm(a,b)=ab/gcd(a,b)=ab/d.
Thus,
c/m is an integer, i.e. m|c
Proof complete.

We are not allow to use fraction in our class for now.

I understand the proof, but is there a way to write the last part without using "/"?

Originally Posted by tttcomrader

We are not allow to use fraction in our class for now.

I love your professor, I do agree with that approach because division is defined only for divisors.

Anyway, this is what you can do in your class...
If a|b then you can write (b/a) as a fraction because it represents the unique number k such that b=ak (which exists by divisibility). (And a not = to 0).

Basically what I did with the division argument embedded in the rationals is this:

Theorem
If a|bc and b|a. Then (a/b)|c (and b is non-zero).

Proof
Again, this is valid in your class, because as mentioned division that exists within the integers just represents the quotient upon division.

By definition, bc=ka and a=bj.
Multiply, equation 2, though by k to get,
ka=bkj
Substitution in equation 1, to get,
bc=bkj
Divide, (for b not = 0)
c=kj
Thus, j|c BUT j=(a/b) by definition.
Q.E.D.

I leave it as an excersice to you to modify my proof using the theorem I just proved right now.
Again, try to understand what I said, I am not dividing, I am just using a/b to represent that value of j. And this is premisible in your class.

Thanks, I finally got it.

KK