Question

In: Computer Science

Problem 1. Using prime factorization, find gcd(900, 140) and lcm(900, 140).


Problem 1. Using prime factorization, find gcd(900, 140) and lcm(900, 140).

Solutions

Expert Solution

Prime factorization of 900 = 2 x 2 x 3 x 3 x 5 x 5
Prime factorization of 140 = 2 x 2 x 5 x 7
To find the GCD, find any prime factors that are in common between the products. Each product contains two 2s and one 5, so use these for the GCD.

-> GCD = 2 x 2 x 5 = 20

mark all the numbers of products that are used in GCD
Prime factorization of 900 = 2 x 2 x 3 x 3 x 5 x 5
Prime factorization of 140 = 2 x 2 x 5 x 7
To find the LCM, multiply the GCD by all the numbers in the products that have not marked (red).

-> LCM = 20 x 3 x 3 x 5 x 7 = 6300

venereology answered 2 years ago
Next > < Previous

Related Solutions

Problem 7. Give the canonical prime factorization of 504
Prime Factorizations Problem 7. Give the canonical prime factorization of 504 Problem 8. Give the canonical prime factorization of 540 Problem 9. Give the canonical prime factorization of 208740. Problem 10. Give the canonical prime factorization of 514395
Let gcd(a, p) = 1 with p a prime. Show that if a has at least...
Let gcd(a, p) = 1 with p a prime. Show that if a has at least one square root, then a has exactly 2 roots. [hint: look at generators or use x^2 = y^2 (mod p) and use the fact that ab = 0 (mod p) the one of a or b must be 0(why?) ]
Find the GCD (5796852, 4585268) using the Euclidian Algorithm..
Find the GCD (5796852, 4585268) using the Euclidian Algorithm..
Find the GCD (5796852, 4585268) using the Euclidian Algorithm..
Find the GCD (5796852, 4585268) using the Euclidian Algorithm..
TITLE PRIME FACTORIZATION USING AN ARRAY-BASED STACK INTRODUCTION This project revisits one of the problems in...
TITLE PRIME FACTORIZATION USING AN ARRAY-BASED STACK INTRODUCTION This project revisits one of the problems in Project 2, and it will re-use a function within the solution developed there. An integer is prime if it is divisible only by itself and 1. Every integer can be written as a product of prime numbers, unique except for their order, called its prime factorization. For example, 1776 = 37 x 3 x 2 x 2 x 2 x 2. DESCRIPTION Design, implement,...
Explain how you can solve the following problems using the QR factorization. (a) Find the vector...
Explain how you can solve the following problems using the QR factorization. (a) Find the vector x that minimizes ||Ax − b1||^2 + ||Ax − b2||^2 . The problem data are the m × n matrix A and two m-vectors b1 and b2. The matrix A has linearly independent columns. If you know several methods, give the most efficient one. (b) Find x1 and x2 that minimize ||Ax1 − b1||^2 + ||Ax2 − b2||^2 . The problem data are the...
Find the biggest “*prime gap” (see definition) from the prime numbers between 1 and 1,000,000. *Prime...
Find the biggest “*prime gap” (see definition) from the prime numbers between 1 and 1,000,000. *Prime gap = the difference between two consecutive primes. The exercise can be completed manually or with a computer program. Whichever seems easiest.
Explain how you can use QR factorization to solve the following problem Find x1 and x2...
Explain how you can use QR factorization to solve the following problem Find x1 and x2 that minimize ||Ax1 − b1||^2 + ||Ax2 − b2||^2. The problem data are the m× n matrix A, and the m-vectors b1 and b2. The matrix A has linearly independent columns.
1) How many positive integers are greater than 140, less than 30800 and relatively prime to...
1) How many positive integers are greater than 140, less than 30800 and relatively prime to 280.
Show that he gcd of 63 and 40 is 1 and find all integer solutions: 63s...
Show that he gcd of 63 and 40 is 1 and find all integer solutions: 63s + 40t = 1. Use the Euclidean algorithm to find the gcd. Then back solve to find s and t. To get full credit, use the format shown in the post below titled Bezout's Theorem. (See the example where we find the gcd of 18 and 5.) Bézout's theorem says "If  d is the gcd of m and n then we can find integers s...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT