For no great reasons these questions popped out of my mind…
1. Take two distinct numbers A,B. Let their gcd be G. Now let me make a statement – “Any number N that is less than G and divides both A and B must divide G also”. Can this statement be proved? Or is there any counter example?
2. Consider two numbers A and B. A is given to be a non-prime. Now will selecting B to be a prime decrease the number of common multiples for A and B?
Cheers
Answer to question 1:-
If we can show that G is a sum of a multiple of A and a multiple of B, our job is done. In fact, G is the smallest possible such positive sum. Let’s prove it.
Let d be the smallest possible positive integer which can be expressed as mA + nB, for some integers m and n. Let as assume, d = G.
We have still not proved that the d = G. Now, if we show that d divides A as well as B, we can conclude that d is a common divisor, and the only d that would satisfy d >= G, would be d = G, because the common divisor can not be greater than G. So, let’s prove that d divides A as well as B.
Let A = qd + r, where q = floor(A/d).
So, r = A – qd = A – q(mA + nB)
or, r = (1 – qm)A – qnB
We know that r < d, since remainder is always less than the divisor. If r is not 0, it would imply that r is a positive sum of a multiple of A and a multiple of B and this would be a contradiction, since we have assumed d as the smallest possible positive integer that can be expessed as a a sum of a multiple of A and a multiple of B. Therefore, r must be 0. So, A = qd and d divides A. Similarly, d divides B. Therefore, as explained earlier, d = G, or mA + nB = G. Hence, if any integer divides A as well as B, it must divide G too. This completes the proof.
Answer to Question 2:-
You can show that a common multiple of A and B is the multiple of lcm(A, B). Considering there are N numbers in all (so, N = infinity), you’ll get N / lcm(A, B) multiples. For a given A and B, lcm(A, B) can not exceed A * B. Thus, for a given A and B, the least number of common multiples can not be less than N / (A * B). Also, note that, lcm(A, B) = A * B, if and only if, A and B are coprime.
Comment by Susam Pal — July 4, 2008 @ 11:04 pm |
Just noticed that some portion of the proof is missing. Probably, it was caused due to the usage of greater than sign which got interpreted as tags. So, I am posting the second paragraph of the first answer again.
Let d be the smallest possible positive integer which can be expressed as mA + nB, for some integers m and n. Let as assume, d is smaller than G. G divides A and G divides B, therefore, G divides d. But this is a contradiction, as G can not divide a positive integer smaller than itself. Therefore, d is greater than or equal to G.
Comment by Susam Pal — July 6, 2008 @ 12:38 am |