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)

Printable View

- Feb 16th 2007, 02:11 PMtttcomraderCongruence 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)

- Feb 17th 2007, 03:14 PMThePerfectHacker
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) - Feb 17th 2007, 04:38 PMThePerfectHacker
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. - Feb 19th 2007, 08:03 AMtttcomrader
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 "/"? - Feb 19th 2007, 08:27 AMThePerfectHacker
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. - Feb 19th 2007, 12:55 PMtttcomrader
Thanks, I finally got it.

KK