# Math Help - GCD Proof

1. ## GCD Proof

Assume GCD(n,b) = 1. Show that if n | ab then n | a.

My professor says: Hint - Use Bezout's identy

Thanks in advance for any help...

2. Originally Posted by jzellt
Assume GCD(n,b) = 1. Show that if n | ab then n | a.

My professor says: Hint - Use Bezout's identy

Thanks in advance for any help...

Hint: You can use xn + yb = 1, where x,y are integers

3. GCD(n,b) = 1 => there exist integers x,z s.t. 1 = nx + bz

now multiply this by a and you'll get: a = anx + abz

n will now divide anx (because of the n) and will divide abz (because of the assumption), so n will divide their sum, i.e. n will divide a.