Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Diophantine Equations/GCD

  1. Mar 13, 2008 #1
    1. The problem statement, all variables and given/known data
    Suppose that gcd(a,b)=1 and that a|n and b|n. Prove that ab|n.

    2. Relevant equations
    Since we know that gcd(a,b)=1, we can say that ax+by=1 for some x,y as elements of the integer set.

    3. The attempt at a solution
    My professor said I should multiply the entire equation by n, but I still can't figure it out. Any help would be appreciated. Thanks in advance.
  2. jcsd
  3. Mar 14, 2008 #2
    I also have another problem that takes priority over this one if anybody can help.

    Prove that (2n)!/(2^n*n!) is an odd number when n is a nonnegative integer.
  4. Mar 14, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    If you multiply the equation by n, you get n=nax+nby. Now use the fact that both a & b divide n.

    For your second problem, have you tried expanding (2n)!/(2^n*n!) out?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook