Suppose A divided by B and the remainder is r1.
2A divided by B and the remainder is r2.
...
...
BA divided by B and the remainder is rB=0.
Properties of r's
1)r<B and an r is a non-negative integer.
2)ri≠rj
There is not any pair of r's which are the same value, otherwise some nA|B. n=|i-j|, and n is surely lesser than B. n is not divisible by B then. We also know that B is not divisible by B too. How can nA be divisible by B? Thus the "otherwise" situation cannot exist, proven.
r1......rB-1 are only B-1 naturals and none of them are equal. Then definitely they are 1, 2, ...B-1 Disordered.
One of them is 1 for sure. And that one gives out the answer.
Oh yes!!!
]]>Let H be the subset of Z consisting of all integer of the form
It is natural that (λA + μB)|hcf(A,B), but whether there exist λ and μ such that λA + μB=hcf(A,B) lies on Bézouts identity.
]]>As in your case, A and B are coprime, that means that you can find λ and μ such that λA + μB adds to anything you want, including 1.
]]>Yeah, proofs of even simple results can sometimes be a bit a messy.
Two proofs are given on the Wikipedia page. The first proof looks short and tidy, but I have doubts about its validity. It uses the result that if p and q are coprime (in other words their highest common factor is 1) and pr ≡ ps (mod q), then the p can be cancelled from both sides, leaving r ≡ s (mod q). This is equivalent to saying that if q divides pk and q and p are coprime, then q divides k. But this is a result which may possibly have to be proved using Bézouts identity which is what is to be proved!! I mean, there may be more than one way of proving the last result, but I can only do it using Bézouts identity. If theres no other way, then the proof would be totally circular.
]]>Is there always a pair of naturals p and q satisfying:
|pA-qB|=1?
So far I know BA-AB=0. Thus you can restrict the range of p to lesser than B and that of q to lesser than A for simplicity.
Anyone has got it?
]]>