Check
1 answer:
You might be interested in
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><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:
- Let
,
- Given <em>x</em>, <em>y</em>, use the division algorithm to write
.
- If r = 0, stop and output <em>y</em>; this is the gcd of a, b.
- If
, 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,
The gcd(621, 82) is 1. Therefore, 621 and 82 are relatively prime.
Step-by-step explanation:
We have 3 given inputs namely P, Q, R and we have to draw a logic circuit which will give the output 1 if , and only if, P and Q have the same value and Q and R have opposite values.
So, first of all we make a truth table for this
P Q R Output(Y)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
From the truth table we can see that the output, Y can be given by
So, the logic circuit for the given logic equation can be drawn as shown fig.
