Math Is Fun Forum
  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,306

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?dizzyup


X'(y-Xβ)=0

Offline

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

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

Re: Strange Natural Number Pair

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,306

Re: Strange Natural Number Pair

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,306

Re: Strange Natural Number Pair

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


X'(y-Xβ)=0

Offline

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

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

Re: Strange Natural Number Pair

Although I don't understand the proof. hmm


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. smile

Yeah, proofs of even simple results can sometimes be a bit a messy. hmm

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!! eek 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. faint

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,306

Re: Strange Natural Number Pair

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


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,306

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.

see this page


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,306

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!!!up

Last edited by George,Y (2007-03-20 02:21:20)


X'(y-Xβ)=0

Offline

Board footer

Powered by FluxBB