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]
3 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]3 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
What is the measure of the indicated angle?
snow_lady [41]

Answer:

110

Step-by-step explanation:

The angles are alternate exterior angles and alternate exterior angles are equal when the lines are parallel

? = 110

5 0
2 years ago
Read 2 more answers
Use long division to express each fraction as a decimal
lawyer [7]

Answer:

Sorry what fraction

Step-by-step explanation:

ez matth

6 0
3 years ago
Read 2 more answers
^2\left(\frac{d}{dx}\left(\frac{\partial }{\partial x}\left(\right)\right)\right)^'\frac{\partial }{\partial x}\left(\log _{ }\l
LenaWriter [7]

Answer:

ok what

Step-by-step explanation:

5 0
3 years ago
Read 2 more answers
A fish tank contains 24 L of water. Water is added to increase the volume by 12.5%. What is the new volume of water in the tank?
Ronch [10]

Answer:

27 L

Step-by-step explanation:

To find 12.5% of 24, move the decimal all the way to the left and multiply 24 by 0.125. You get 3, which is how much was added to the original volume.

24 + 3 = 27, which is the new volume.

6 0
3 years ago
Larry has read 31 pages of his library book. The book contains p total pages.
OLEGan [10]

Answer:

31 u jest read it

Step-by-step explanation:

6 0
3 years ago
Other questions:
  • Which exponential function is represented by the graph? f(x) = 2(1/2)^x          f(x) = 1/2(2)^x               f(x) = 1/2 (1/2)^
    15·2 answers
  • Is this correct ? .......................
    10·1 answer
  • A rectangular prism is 6 feet long, 5 feet wide, and 7 feet tall. What is the surface area in square inches?
    7·1 answer
  • (02.01 LC) Each person in a simple random sample of 1,200 received a survey, and 325 people returned their survey. How could non
    8·1 answer
  • A container of oregano is 17 pounds heavier than a container of peppercorns. Their total weight is 253 pounds. The peppercorns w
    5·1 answer
  • Someone plz help me with this
    13·2 answers
  • What is the value of x?<br> 1/3 \2 units <br> 1/2 /3 units<br> 2 \ 3 units <br> 3. / 2 units
    6·1 answer
  • Question: <br> Find the Vertex<br> 3. y= x*2+ 18х - 75<br><br> a) (-6,9)<br> b) (9,-6)<br> c) (9,6)
    15·2 answers
  • Which of the following is not a perfect square A)49 B)121 C)144 D)88
    11·1 answer
  • Find the value P(7, 2) probability ​
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!