Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

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

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

i.e.

A=5,B=3 A-2B

A=19,B=4 A-3B

**X'(y-Xβ)=0**

Offline

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

i.e.

A=19,B=7

3A-8B=-1

**X'(y-Xβ)=0**

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

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

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

Thank you very much, JaneFairfax!! You've helped me a lot!!!

**X'(y-Xβ)=0**

Offline

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

Although I don't understand the proof.

**X'(y-Xβ)=0**

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

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

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

Wikipedia isn't Mr. Know All or Ms. Correct.

**X'(y-Xβ)=0**

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

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

**Stanley_Marsh****Member**- Registered: 2006-12-13
- Posts: 345

Here is another version of proof from my textbook

Let H be the subset of Z consisting of all integer of the form

Then H is a subgroup of Z and . By theorem ",Let H be a subgroup of the integers under addition, There exist a unique nonnegative integer d such that H is the set of all multiples of d , that is ", there exists a unique positvie integer d drag that H=dZ, that is , H consists of all multiples of d , In particular , every integer is a multiple of d , and so d is a common divisor of A. Since , there exist integers

*Last edited by Stanley_Marsh (2007-03-15 05:58:59)*

Numbers are the essence of the Universe

Offline

**Stanley_Marsh****Member**- Registered: 2006-12-13
- Posts: 345

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

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,306

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**