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...
Follow Math Help Forum on Facebook and Google+
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
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.
View Tag Cloud