## Friday, April 9, 2010

### An Interesting Property of Relatively-Prime Numbers

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.

1. One should use the following fact from number theory:
GCD(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???

2. A={k,k+a,k+2a,....,k+(b-1)a}
B={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

3. I will analyze the solution by Anonymous.
Here is my solution:
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
If n(A∩B)>1, then there exist p and q such that
1 <= p < q <= N.
=> LCM(a, b) <= q-p < N = ab.

Does anybody see any problem in the above proof?

4. Andrew:
There 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.

5. you say:if n(A,B)=0 then LCM(a,b)>N=ab
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

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

7. Yu:
According 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.

8. "and x ≡ m (mod b) "
must be:
"and y ≡ m (mod b) "

is that right?

9. x and y are the same.

10. Yu, re-typed your solution. Let us know if you see a problem:
----------
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.

11. It is not necessary to re-typed the solution. We are solving the two equations for x.
y appeared in the original problem to highlight that one x is in A and the other in B. YU

12. Yu,
When 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.

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