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)
We can find two positive integers: x,y
Such that: lcm(a,b)=xy and x|a , y|b and gcd(x,y)=1
f = g (mod a)
Then it is true from any divisor of "a" let x|a then:
f = g (mod x)
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)
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).
Since d=gcd(a,b) a powerful theorem says we can find integers x,y such that,
Now, it is trivial to see that,
ab|acx and ab|bcy.
ab|(acx+bcy) i.e. ab|cd
Now the result is immediate.
We can write the fraction (which is an integer) as,
c/m is an integer, i.e. m|c
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:
If a|bc and b|a. Then (a/b)|c (and b is non-zero).
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,
Substitution in equation 1, to get,
Divide, (for b not = 0)
Thus, j|c BUT j=(a/b) by definition.
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.