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.

13 comments:

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

    ReplyDelete
  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

    ReplyDelete
  3. I will analyze the solution by Anonymous.
    Here 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?

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

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

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

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

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

    is that right?

    ReplyDelete
  9. x and y are the same.

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

    ReplyDelete
  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

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

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

    ReplyDelete