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

DrAlexMV

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!

jgens

Use the following fact: If gcd(a,c)=1, then ax+cy=1 for some integers x,y.