Question

In: Math

A. 271 and 516 1. Find the greatest common divisor, d, of the two numbers from part...

A. 271 and 516

1. Find the greatest common divisor, d, of the two numbers from part A using the Euclidean algorithm. Show and explain all work.

2. Find all solutions for the congruence ax ? d (mod b) where a and b are the integers from part A and d is the greatest common divisor from part A1. Show and explain all work.

Expert Solution

271 and 516

Step 1

A=271, B=516
A ?0
B ?0
Use long division to find that 516/271 = 1 with a remainder of 245. write this as: 516 = 271 * 1 + 245
Find GCD(271,245), since GCD(516,271)=GCD(271,245)

A=271, B=245

Step 2

A ?0
B ?0
Use long division to find that 271/245 = 1 with a remainder of 26. Write this as: 271 = 245 * 1 + 26
Find GCD(245,26), since GCD(271,245)=GCD(245,26)

A=245, B=26

Step 3

A ?0
B ?0
Use long division to find that 245/26 = 9 with a remainder of 11. Write this as: 245 = 26 * 9 + 11
Find GCD(26,11), since GCD(245,26)=GCD(26,11)

A=26, B=11

Step 4

A ?0
B ?0
Use long division to find that 26/11 = 2 with a remainder of 4. Write this as: 26 = 11 * 2 + 4
Find GCD(11,4), since GCD(26,11)=GCD(11,4)

A=11, B=4

Step 5

A ?0
B ?0
Use long division to find that 11/4 = 2 with a remainder of 3. Write this as: 11 = 4 * 2 + 3
Find GCD(4,3), since GCD(11,4)=GCD(4,3)

A=4, B=3

Step 6

A ?0
B ?0
Use long division to find that 4/3 = 1 with a remainder of 1. Write this as: 4 = 3 * 1 + 1
Find GCD(3,1), since GCD(4,3)=GCD(3,1)

A=3, B=1

Step 7

A ?0
B ?0
Use long division to find that 3/1 = 3 with a remainder of 0. Write this as: 3 = 3 * 1 + 0
Find GCD(1,0), since GCD(3,1)=GCD(1,0)

A=1, B=0

Step 8

A = 0
B ?0

so GCD (516,271) = 1

milcah answered 2 years ago

Java program: Greatest Common Divisor Write a program which finds the greatest common divisor of two...

Java program: Greatest Common Divisor Write a program which finds the greatest common divisor of two natural numbers a and b Input: a and b are given in a line separated by a single space. Output: Output the greatest common divisor of a and b. Constraints: 1 ≤ a, b ≤ 109 Hint: You can use the following observation: For integers x and y, if x ≥ y, then gcd(x, y) = gcd(y, x%y) Sample Input 1 54 20 Sample Output...

Activity 6. Write a Prolog definition of the greatest common divisor of two numbers. Then use...

Activity 6. Write a Prolog definition of the greatest common divisor of two numbers. Then use it to compute gcd(4, 10), gcd(15, 36), and gcd(25, 55). Activity 7. Write a Prolog program to find the last item in a list. give me the screenshot pls

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1....

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1. Prove that there is a natural number k such that n divides ((m^k) − 1).

Let a and b be positive integers, and let d be their greatest common divisor. Prove...

Let a and b be positive integers, and let d be their greatest common divisor. Prove that there are infinitely many integers x and y such that ax+by = d. Next, given one particular solution x0 and y0 of this equation, show how to find all the solutions.

Find the greatest common divisor d = gcd(527, 341). Show all calculation steps. We assume that...

Find the greatest common divisor d = gcd(527, 341). Show all calculation steps. We assume that the modulus is a positive integer. But the definition of the expression a mod n also makes perfect sense if n is negative. Determine the following: a. 7 mod 4 b. 7 mod -4 c. -7 mod 4 d. -7 mod -4

Write a C function gcd that returns the greatest common divisor of two integers. The greatest...

Write a C function gcd that returns the greatest common divisor of two integers. The greatest common divisor (GCD) of two integers is the largest integer that evenly divides each of the two numbers.

4. (a) Use the Euclidean algorithm to find the greatest common divisor of 21 and 13,...

4. (a) Use the Euclidean algorithm to find the greatest common divisor of 21 and 13, and the greatest common divisor of 34 and 21. (b) It turns out that 21 and 13 is the smallest pair of numbers for which the Euclidean algorithm requires 6 steps (for every other pair a and b requiring 6 or more steps a > 21 and b > 13). Given this, what can you say about 34 and 21? (c) Can you guess...

The greatest common divisor of two integers x and y is the largest positive integer that...

The greatest common divisor of two integers x and y is the largest positive integer that evenly divides both. For example, gcd(12,6)=6, gcd(21,14)=7, gcd(31,10)=1, gcd(55,25)=5 Recall that the gcd of two integers is gcd(a,0) = a gcd(a,b) = gcd(b, a%b) Create int gcd(int x, int y). Assume that the two integers are zero or positive. Write the code as a pure function. Put it in a file gcd.c. Of course, you will need to test it. The function Φ(n) counts...

In C++ The greatest common divisor (GCD) of two integers in the largest integer that evenly...

In C++ The greatest common divisor (GCD) of two integers in the largest integer that evenly divides each of the numbers. Write a function called GCD that has a void return type, and accepts 3 parameters (first two by value, third by reference). The function should find the greatest common divisor of the first two numbers, and have the result as its OUTGOING value. Write a main function that asks the users for two integers, and uses your function to...

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf)...

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. The greatest common divisor of a and b is written as gcd (a, b), or sometimes simply as (a, b). For example, gcd (12, 18) = 6, gcd (−4, 14) = 2 and gcd (5, 0) = 5. Two numbers are called co-prime or relatively prime...