I have no idea how to write this proof, not even sure how tostart. I can only us
ID: 2938738 • Letter: I
Question
I have no idea how to write this proof, not even sure how tostart. I can only use the induction or WOPmethods. "Two numbers are said to be relatively prime if their gcd is1. Prove that a and b are relatively prime if and only ifevery integer can be written as a linear combination of a andb." Please show me what this proof will look like. Thanks somuch! I have no idea how to write this proof, not even sure how tostart. I can only use the induction or WOPmethods. "Two numbers are said to be relatively prime if their gcd is1. Prove that a and b are relatively prime if and only ifevery integer can be written as a linear combination of a andb." Please show me what this proof will look like. Thanks somuch!Explanation / Answer
QuestionDetails: I have no idea how to write this proof, not even sure how tostart. I can only use the induction or WOPmethods. "Two numbers are said to be relatively prime if their gcd is1. Prove that a and b are relatively prime if and only ifevery integer can be written as a linear combination of a andb." Please show me what this proof will look like. Thanks somuch!GIVEN...A AND B ARE RELATIVELY PRIME
TPT WE CAN WRITE ANY INTEGER I AS EQUAL TO
I=AP+BQ....THAT IS TPT
AX+BY =1 WHERE X AND Y ARE INTEGERS SO THAT ANY INTEGER I CAN THENBE WRITTEN AS
I=AIX+BIY=AP+BQ AS NEEDED.....WHERE .....P=IX AND Q=IY
AS PER EXISTENCE AND UNIQUENESS THEOREM ON GCD OFINTEGERS
AX+BY=1 IF GCD OF A AND B=1[IF YOU WANT PROOF OF THIS STD. THEOREMPLEASE POST
SEPARATELY]...PROVED
CONVERSELY
LET
AX+BY=1
TPT GCD[A,B]=1
LET [A,B]=D
D|A...D|B
D|(AX+BY)=1...
HENCE D=±1
BUT GCD IS TAKEN AS POSITIVE AS A RULE.
HENCE D=1
HENCE
AX+BY=1...PROVED