Let a b be nonnegative integers not both zero Define the set

Let a, b be nonnegative integers, not both zero. Define the set I(a, b) = {ax + by : x, y Z}. (Thus, I(a,b) is the set of all linear combinations of a,b, with coefficients from Z. The letter I stands for ideal, which is a concept we will meet later in the course.)

(a) Show that if a,b,q,r are integers with a=bq+r, then I(a,b)=I(b,r).

(b) Explain why (a) implies that I (a, b) = I (0, gcd(a, b)).

(c) Deduce from (b) that there are integers x and y with gcd(a, b) = ax + by.

Solution

Ideal I is a subset of a ring R that forms an additive group and has the property whenever x belongs to R and y belongs to I then xy and yx belong to I.

We have that according to euclid algorithm 2 non zero numbers a and b is also their smallest positive integral linear combination that is smallest positive number of the form a+bq. The ideal generated by a and b is the ideal generated by g alone.(An ideal generated by a single element is principal ideal).

a) If a,b,q,r are integers with a=bq+r then I(a,b)=a=bq+r (1) where I the ideal has the gcd g which satidfies (1) and (2) let I(b,r)=b=rq+s(2)

If I is non zero ideal choose the smallest element a in the ideal I. If b is any other element then the gcd(a,b) is in I and should be either + or - a so b is multiple of a.

b) The greatest common divisor of 2 integers a and b not both zero is the largest positive integer which dicvides both a and b we have g(0,0)=0 by convention .If a=0 then gcd(a,b)=b and gcd(0,b)=b similarly I(a,b)= I(0,gcd(a,b)).

c) let x and y be integers such that D={ax+by:x,y belongs to Z}intersection (N/{0}) then let x=a and y=b then a^2+b^2 belongs to D there is a element d belonging to D such that d=gcd(a,b) since d belongs to D then x,y belongs to Z ,d=ax+by every element can be written in ax+by belonging to Z for x,y belongs to Z which is divisible by d.