You are not logged in.
Pages: 1
A and B are both natural numbers.
A>B; B≠1; A and B have no common factor except 1 (not both even for sure).
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?
X'(y-Xβ)=0
Offline
i.e.
A=5,B=3 A-2B
A=19,B=4 A-3B
X'(y-Xβ)=0
Offline
i.e.
A=19,B=7
3A-8B=-1
X'(y-Xβ)=0
Offline
Yes. Its called Bézouts identity.
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
Last edited by JaneFairfax (2007-03-14 20:09:57)
Offline
Thank you very much, JaneFairfax!! You've helped me a lot!!!
X'(y-Xβ)=0
Offline
Although I don't understand the proof.
X'(y-Xβ)=0
Offline
Youre welcome.
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.
Last edited by JaneFairfax (2007-03-14 20:43:01)
Offline
Wikipedia isn't Mr. Know All or Ms. Correct.
X'(y-Xβ)=0
Offline
For two natural numbers A and B, you can use Euclid's algorithm to find integers λ and μ such that λA + μB = k*hcf(A,B), where k is an integer.
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.
Why did the vector cross the road?
It wanted to be normal.
Offline
But first paragraph is derived from the latter.
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.
X'(y-Xβ)=0
Offline
Here is another version of proof from my textbook
Let H be the subset of Z consisting of all integer of the form
Last edited by Stanley_Marsh (2007-03-15 05:58:59)
Numbers are the essence of the Universe
Offline
According to above , the two numbers of yours , (A,B)=1 , then there must be p,q such that Ap+Bq=gcd(A,B)=1
Numbers are the essence of the Universe
Offline
I've got the answer, simple one:
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!!!
Last edited by George,Y (2007-03-20 02:21:20)
X'(y-Xβ)=0
Offline
Pages: 1