1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof for: If a|bc, then a|b.

  1. Mar 18, 2012 #1
    In my Discrete Mathematics class we are are covering divisibility. One of the problems that the professor covered (quite terribly) is the following:

    1. The problem statement, all variables and given/known data

    Prove or salvage:

    If a|bc, then a|b.

    2. Relevant equations

    Relevant concepts:

    Relatively prime numbers
    Divisibility

    3. The attempt at a solution

    I know that the statement is wrong as it is. I also know that in order to salvage the statement, I must say that a and c are relatively prime. The problem is that I do not know how to rigorously prove this.

    Could somebody guide me in how to do this. Teach a man to fish!
     
  2. jcsd
  3. Mar 18, 2012 #2

    jgens

    User Avatar
    Gold Member

    Use the following fact: If gcd(a,c)=1, then ax+cy=1 for some integers x,y.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook