Find a,b belongs to Z such that a*43+b*47= 1

Question

 what is and a and b if ax43 + bx47=1. Please show me the steps I really want to know how to go about a problem like this. I got this wrong on the latest exam and my professor never goes over the exams. Thank you!

Answer 1

Use the Euclidean Algorithm to find the GCD of 43 and 47.  Of course, 43 and 47 are both prime so you already know that their GCD is 1, but you need the steps from the algorithm to determine a and b.  I assume you are familiar with the algorithm so I only list the summary output from it below.  

 

47 = 43*1 + 4

43 = 4*10 + 3

 4  = 3*1 + 1

 3  = 1*3 + 0  

 

The 0 remainder indicates the termination of the algorithm.  The last non-zero remainder (1 from the line above) is the GCD.  To write the GCD in the form 1 = 43a + 47b start from the penultimate line and work backwards.  

 

1 = 4 - 1*3                          (penultimate line, solved for remainder = 1)

1 = 4 - 1*(43 - 10*4)           (replace 3 with its value from 43 = 4*10 + 3)

1 = -1*43 + 11*4                 (rearrange terms)

1 = -1*43 + 11*(47 - 1*43)  (replace 4 with its value from 47 = 43*1 + 4)

1 = -12*43 + 11*47             (rearrange terms)  

 

which is the desired result with a = -12 and b = 11.

Answer 2

43a + 47b = 1

 

There are many answers to this but probably the simples

way is to just make both fractions equivalent to 1/2 so

that you have 1/2 + 1/2 = 1

 

43a = 1/2

a = (1/2)/43 = (1/2)(1/43) = 1/86

 

47b = 1/2

b = (1/2)/47 = (1/2)(1/47) = 1/94

 

Check:  43a + 47b = 1

           43(1/86) + 47(1/94) = 1

           1/2 + 1/2 = 1

           1=1

 

This is only one out of infinite solutions to this problem.

You could have set 43a = 1/4 and 47b = 3/4 just as easily... etc.