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

    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


    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

Similar Threads - Proof a|bc Date
Lim sup proof Mar 12, 2018
Real Analysis Proof Mar 11, 2018
Proof that a recursive sequence converges Mar 8, 2018
Bland rule proof linear programming Mar 7, 2018
Implicit Euler ODE BC Oct 25, 2017