In Number Theory Prove If ab1 and d a d divide a then db1 H

In Number Theory

Prove:

If (a,b)=1 and d | a (d divide a) then (d,b)=1

Hint: Use Unique Factorization Theorm

Solution

By the Euclidean Algorithm there are integers X and Y so that aX + bY = gcd(a,b) = 1.

Since d divides a then a/d is an integer and so is aX/d.

Then dX\' + bY = 1 with X\' = aX/d.

Since gcd(d,b) divides both d and b then gcd(d,b) divides dX\' + bY = 1, so gcd(d,b) = 1.

Or

a=1,b=1 given (a,b)=1

Let a/d=1

1/d=1

Then d=1.

Since d/a=1

d/1=1

d=1

Hence by this (d,b)=1is proved.