Prove the following proposition Let b be an integer Then gcd

Prove the following proposition: Let b be an integer. Then gcd(a, b) {1, |b|} for every a E Z if and only if b is prime, -b is prime, or b {-1, 1}.

Solution

Let gcd(a,b) = {1,|b|} for every integer a

If gcd(a,b) = 1 then b is coprime to every integer a and hence b is prime or b is 1

If b is prime then -b is also prime and so is -1 and hence the result

If gcd(a,b) = |b| => |b| divides a and b

a = |b|t and b = |b| r

=> gcd (a/|b|, b/|b|) = 1

=> a/|b| and b/|b| are prime to each other or a/|b|, 1 are prime

Hence b or -b is prime or b is {-1,1}

Now suppose b is prime

Then gcd(a,b) = 1 for all integers a

If -b is prime then gcd(a,-b) = 1 for all integers a and hence gcd (a,b) = 1

If b is in { -1, 1} then also gcd(a,1) =1 and gcd(a,-1) = 1 for all integers a