Hello Guys,

There are a few more parabola questions in line, but I need to solve a number theory question. I have a proof but it is very long and clumsy. I am looking for a slicky solution. Here it goes:

a and b are relatively-prime integers such as,

3 and 8 (e.g. GCD(3,8)=1).

Let N=ab.

Let 1 ≤ k ≤ a, and 1 ≤ m ≤ b, both are integers.

Let set A be all integers, x=k+ia AND x ≤ N AND i=0,1,...

Let set B be all integers, y=m+jb AND y ≤ N AND j=0,1,...

PROVE THAT A∩B contains one integer only.

Example:

a=3, b=8, GCD(3,8)=1

N=24

Let k=2 and m=6.

A={2, 5, 8, 11, 14, 17, 20, 23}

B={6, 14, 22}

A∩B={14}

Note that the above statement is true for any k and m satisfying

1≤k≤a, and 1≤m≤b respectively.

It is very obvious that there should be a short and beautiful proof.

One should use the following fact from number theory:

ReplyDeleteGCD(a,b) * LCM(a,b) = ab.

Here,

GCD: Greatest Common Divisor and

LCM: Lowest Common Multiplier

Since a and b are relatively prime => GCD(a,b)=1

=> LCM(a,b)= ab = N.

So what's next???

A={k,k+a,k+2a,....,k+(b-1)a}

ReplyDeleteB={m,m+b,m+2b,....,m+(a-1)b}

if

m+jb=r mod a and m+lb=r mod a (j>l)

then (j-l)b=0 mod a

a divides (j-l) but 0<j-l<a

two elements of B cannot have the same remainder

mod a

B has a elements

only one remainder = k (if r=0, k=a)

m+jb=k+ia

I will analyze the solution by Anonymous.

ReplyDeleteHere is my solution:

(PROOF BY CONTRADICTION)

We aleady know that: LCM(a,b)= ab = N

ASSUME that n(A∩B)<>1.

In other words, assume that

either n(A∩B)=0 OR n(A∩B)>1

If n(A∩B)=0, then LCM(a,b)>N=ab

=> CONTRADICTION.

If n(A∩B)>1, then there exist p and q such that

1 <= p < q <= N.

=> LCM(a, b) <= q-p < N = ab.

=> CONTRADICTION.

Does anybody see any problem in the above proof?

Andrew:

ReplyDeleteThere are b elements in A, and a elements in B.

Since gcd(a,b) = 1, the values of m+jb reduced modulo a must span all values in the interval [0,a), occuring in a pattern with period a.

Since the set B contains a consecutive terms of the pattern (i.e. a whole period), each modulated value will occur exactly once. The term whose modulated value is k, will be the single element in A∩B.

you say:if n(A,B)=0 then LCM(a,b)>N=ab

ReplyDeletewhat do you think about this:

a=4,k=1,b=6,m=2

N=24,LCM(4,6)=12

A={1,5,9,13,17,21}

B={2,8,14,20}

n(A,B)=0

But a=4 and b=6 are not relatively prime numbers. That's why you can alternate elements of A and B without "touching" each other.

ReplyDeleteYu:

ReplyDeleteAccording to the Chinese remainder theorem, if a and b are relatively-prime, then x ≡ k (mod a) and x ≡ m (mod b) have a unique solution modulo ab, i.e. x = p+n(ab), where p ≤ ab and n=0,1,2...

Since x ≤ ab, .: x = p. Hence n(A∩B)=1.

"and x ≡ m (mod b) "

ReplyDeletemust be:

"and y ≡ m (mod b) "

is that right?

x and y are the same.

ReplyDeleteYu, re-typed your solution. Let us know if you see a problem:

ReplyDelete----------

According to the Chinese remainder theorem, if a and b are relatively-prime,

then the system {x≡k (mod a), y≡m (mod b), x=y} has a unique solution modulo ab, i.e.,

x=y=p+c(ab), where p≤ab, and c=0, 1,.... Since x ≤ab, then x=y=p. Hence n(A∩B)=1.

It is not necessary to re-typed the solution. We are solving the two equations for x.

ReplyDeletey appeared in the original problem to highlight that one x is in A and the other in B. YU

Yu,

ReplyDeleteWhen I wrote "Yu, re-typed your solution", I meant "Yu, I re-typed your solution". So it was not in a command form. Sorry about that. Your solution is pretty good and complete.

Thank you.

Apparently it was not in a command form because you have done the re-typing in your post. Thanks. YU

ReplyDelete