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

You are not logged in.

## #1 2007-03-14 19:05:28

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

### Strange Natural Number Pair

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

## #2 2007-03-14 19:12:22

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

i.e.
A=5,B=3 A-2B
A=19,B=4 A-3B

X'(y-Xβ)=0

Offline

## #3 2007-03-14 20:03:58

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

i.e.
A=19,B=7
3A-8B=-1

X'(y-Xβ)=0

Offline

## #4 2007-03-14 20:09:01

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

### Re: Strange Natural Number Pair

Yes. Its called Bézouts identity.

http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

Last edited by JaneFairfax (2007-03-14 20:09:57)

Offline

## #5 2007-03-14 20:14:50

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

### Re: Strange Natural Number Pair

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

X'(y-Xβ)=0

Offline

## #6 2007-03-14 20:19:23

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

### Re: Strange Natural Number Pair

Although I don't understand the proof.

X'(y-Xβ)=0

Offline

## #7 2007-03-14 20:41:22

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

### Re: Strange Natural Number Pair

Youre 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 prps (mod q), then the p can be cancelled from both sides, leaving rs (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ézouts 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ézouts identity. If theres no other way, then the proof would be totally circular.

Last edited by JaneFairfax (2007-03-14 20:43:01)

Offline

## #8 2007-03-14 23:58:42

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

### Re: Strange Natural Number Pair

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

X'(y-Xβ)=0

Offline

## #9 2007-03-15 00:07:06

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

### Re: Strange Natural Number Pair

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

## #10 2007-03-15 02:12:42

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

### Re: Strange Natural Number Pair

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ézouts identity.

X'(y-Xβ)=0

Offline

## #11 2007-03-15 05:52:36

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

### Re: Strange Natural Number Pair

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

## #12 2007-03-15 06:00:24

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

### Re: Strange Natural Number Pair

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

## #13 2007-03-20 02:17:58

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

### Re: Strange Natural Number Pair

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