1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
CaHeK987 [17]
2 years ago
7

Use the Euclidean Algorithm to compute the greatest common divisors indicated. (a) gcd(20, 12) (b) gcd(100, 36) (c) gcd(207, 496

)
Mathematics
1 answer:
coldgirl [10]2 years ago
3 0

Answer:

(a) gcd(20, 12)=4

(b) gcd(100, 36)=4

(c) gcd(496,207 )=1

Step-by-step explanation:

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, without explicitly factoring the two integers.

The Euclidean algorithm solves the problem:

<em>                                   Given integers </em>a, b<em>, find </em>d=gcd(a,b)<em />

Here is an outline of the steps:

  1. Let a=x, b=y.
  2. Given x, y, use the division algorithm to write x=yq+r.
  3. If r=0, stop and output y; this is the gcd of a, b.
  4. If r\neq 0, replace (x,y) by (y,r). Go to step 2.

The division algorithm is an algorithm in which given 2 integers N and D, it computes their quotient Q and remainder R.

Let's say we have to divide N (dividend) by D (divisor). We will take the following steps:

Step 1: Subtract D from N repeatedly.

Step 2: The resulting number is known as the remainder R, and the number of times that D is subtracted is called the quotient Q.

(a) To find gcd(20, 12) we apply the Euclidean algorithm:

20 = 12\cdot 1 + 8\\ 12 = 8\cdot 1 + 4\\ 8 = 4\cdot 2 + 0

The process stops since we reached 0, and we obtain gcd(20, 12)=4.

(b) To find gcd(100, 36) we apply the Euclidean algorithm:

100 = 36\cdot 2 + 28\\ 36 = 28\cdot1 + 8\\ 28 = 8\cdot 3 + 4\\ 8 = 4\cdot 2 + 0

The process stops since we reached 0, and we obtain gcd(100, 36)=4.

(c) To find gcd(496,207 ) we apply the Euclidean algorithm:

496 = 207\cdot 2 + 82\\ 207 = 82\cdot 2 + 43\\ 82 = 43\cdot 1 + 39\\ 43 = 39\cdot 1 + 4\\ 39 = 4\cdot 9 + 3\\ 4 = 3\cdot 1 + 1\\ 3 = 1\cdot 3 + 0

The process stops since we reached 0, and we obtain gcd(496,207 )=1.

You might be interested in
If y varies inversely as x, and y=6 when x=3. Then find the value of y when x=32
s2008m [1.1K]

Answer: y = 18/32


Step-by-step explanation: Okay the equation is xy = k

You plug in x and y.

(3)(6) = k

18 = k

To get the value of y when x = 32 you plug in 32.

Use this equation now y = k/x

Now it is y = 18/32

And that is your answer!


7 0
3 years ago
What is 6x+3y=-15 in y-intercept form
iren2701 [21]

Answer:

3y = -6x - 15

Step-by-step explanation:

To put 6x + 3y = -15 into Slope Intercept Form you need to know the formula (y = mx + b) so we know we need to get y on its own side so we can -6x  from both side giving us 3y = -6x +-15 or 3y = -6x - 15 There are many different slope intercept forms for this equation depending on how you get y by its self!

8 0
3 years ago
Read 2 more answers
Simplified fraction of 49 out of 112
SVETLANKA909090 [29]
The simplified fraction of 49\112 is 7/16. This results from you finding a common number which can divide into 49 and 112 equally. In this case the number is 7. Resulting in the answer 7/16.
7 0
3 years ago
Read 2 more answers
I am stuck on this question please help me:)
12345 [234]

Answer:

Step-by-step explanation:

the answer is 270

hope this helps

4 0
2 years ago
Read 2 more answers
If PS = 2x + 18 and QR = 5x - 9, solve for x.
Alexxx [7]

Answer:

2x+18+5x-9

2x+5x18-9

<u>7</u><u>x</u>+<u>9</u>

7. 7

x= 1.4

hope it helps

4 0
3 years ago
Other questions:
  • If you roll a 6 sided die 4 times what is the probability of getting 3 2’s
    8·1 answer
  • Solve for x : 2^x+4^x+8^x=−14
    15·1 answer
  • 3 + 2(2x + 8) = 1 is equivalent to
    13·1 answer
  • Write the equition of the line that passes through the pair of points (8,-8) and (9,-4)
    14·1 answer
  • Which are the ordered pairs?
    5·1 answer
  • The scale for a map is 20 miles = 1/2 inch. The distance between two towns on the map is 3 3/4 inches. What is the actual distan
    15·1 answer
  • PLEASE HELP
    14·1 answer
  • Math Exit Slip: Value-Mart is having a back -to - school sale on pencils. A pack of of 20 sells for $7.97, whereas a 12-pack cos
    13·1 answer
  • 3x + 2x – x + 2x² = <br> Please help !!
    12·1 answer
  • henry is organizing textbooks on his bookshelf. he has a spanish textbook, a math textbook, and a history textbook. how many dif
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!