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
Diano4ka-milaya [45]
3 years ago
10

Use the Euclidean Algorithm to demonstrate that 621 and 82 are relatively prime to each other. Explain.

Mathematics
1 answer:
8090 [49]3 years ago
5 0

Answer:

621 and 82 are relatively prime.

Step-by-step explanation:

Two integers are relatively prime (or coprime) if there is no integer greater than one that divides them both (that is, their greatest common divisor is one).

The greatest common divisor of two integers <em>a</em> and <em>b</em> is the largest integer that divides them both.

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 a, b find </em>d=gcd(a,b)<em />

The Euclidean algorithm provides a fast way to determine <em>d</em> without knowing the prime factors of <em>a</em> or <em>b</em>. Here is an outline of the steps:

  1. Let a=x, b=y
  2. Given <em>x</em>, <em>y</em>, use the division algorithm to write x=yq+r, \quad 0\leq r\leq |y|.
  3. If r = 0, stop and output <em>y</em>; this is the gcd of a, b.
  4. If r \neq 0, replace (<em>x, y</em>) by (<em>y, r</em>). 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 until we get a result that lies between 0 (inclusive) and D (exclusive) and is the smallest non-negative number obtained by repeated subtraction.

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.

Applying the above steps,

621-82=539\\539-82=457\\457-82=375\\375-82=293\\293-82=211\\211-82=129\\129-82=47\\\\621=82\cdot7+47

621 = 82\cdot 7 + 47\\ 82 = 47\cdot 1 + 35\\ 47 = 35\cdot1 + 12\\ 35 = 12\cdot2 + 11\\ 12 = 11\cdot1 + 1\\ 11 = 1\cdot11 + 0

The gcd(621, 82) is 1. Therefore, 621 and 82 are relatively prime.

You might be interested in
Karman's Floral Shop has determined that the cost of production for one floral arrangement is $10.00. The shop charges $25.00 pe
Schach [20]
15 dollars because you subtract production cost from what is charged
4 0
3 years ago
Read 2 more answers
If I did 2 tests a month for four months how many would I get done a month how many would I get done in four months.
AfilCa [17]

Answer: 2 per month

8 per four months

Step-by-step explanation:

6 0
3 years ago
Read 2 more answers
180 miles in 3 hours, what's the unit rate?
Oliga [24]

Answer:

60 or 60:1

Step-by-step explanation:

You will have to divide 180 by 3 which is 60 or you can divide 160 / 3 = 60 & divide 3 / 3 = 1.

6 0
3 years ago
Read 2 more answers
What’s the answer to 8-(-4)
mash [69]

Answer:

+ 12

Step-by-step explanation:

8 - (- 4) = 8 + 4 = 12

8 0
3 years ago
Read 2 more answers
A piggy bank contains a nickels, dimes and quarters. There are five more dimes than nickels and twice as many quarters as dimes.
Natasha2012 [34]

Answer:

34 nickels, 39 dimes, 78 quarters

Step-by-step explanation:

q = quarters, d = dimes, n = nickels

n = d - 5

q = 2d

.25q + .10d + .05n = 7.55

<em>Plug in the first 2 equations into the third one</em>

.5d + .10d + .05(d - 5) = 7.55

<em>Open up the Parenthesis</em>

.5d + .10d + .5d - .25 = 7.55

<em>Combine Like Terms</em>

.2d - .25 = 7.55-->

.2d = 7.8 -->

d = 39 -->

n = 39 - 5 = 34

q = 2(39) = 78

4 0
3 years ago
Other questions:
  • The variable Z is directly proportional to X. When X is 5, Z has the value 55.
    11·2 answers
  • True or false;<br> If two planes cross one another, then their intersection is two lines.
    15·2 answers
  • If you multiply an inequality by a negative number _____.
    6·1 answer
  • mary bought a bag of jelly beans there were 24 green ones which made up 8% of all the jelly beans in the bag howmany jelly beans
    13·1 answer
  • Mr. Mustard said: "If you add the ages of my
    10·1 answer
  • Don't steal points
    7·2 answers
  • can someone help me please
    12·1 answer
  • Hey if anyone can help me and explain add my on discord !! “— hisdoll#1356”
    11·1 answer
  • Express sin P as a fraction in simplest terms.​
    7·2 answers
  • What is the answer to this question?
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!