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.

14 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
  14. Do not use all of these Private Money Lender here.They are located in Nigeria, Ghana Turkey, France and Israel.My name is Mrs.Ramirez Cecilia, I am from Philippines. Have you been looking for a loan?Do you need an urgent personal or business loan?contact Fast Legitimate Loan Approval he help me with a loan of $78.000 some days ago after been scammed of $19,000 from a woman claiming to be a loan lender from Nigeria but i thank God today that i got my loan worth $78.000.Feel free to contact the company for a genuine financial call/whats-App Contact Number +918929509036 Email:(fastloanoffer34@gmail.com)

    ReplyDelete