Question

See four problems attached. These will ask you to think about GCDs and prime factorizations, and also look at the related topic of Least Common Multiples (LCMs).

The prime factorization of numbers can be used to find the GCD. If we write the prime factorization of a and b as a = p a1 1 p a2 2 · p an n b = p b1 1 p b2 2 · p bn n (using all the primes pi needed to write either factorization), then gcd(a, b) is gcd(a, b) = p min(a1,b1) 1 p min(a2,b2) 2 . . . pmin(an,bn) n . (In other words, choose the smaller power required for either a or b.) For example, the prime factorization of 289 and 85 are given as follows: 289 = 172 85 = 51 171 Note that 85 needs a 5, but 289 doesn’t. However, we can rewrite the factorization as 289 = 172 = 50 172 85 = 5 · 17 = 51 171 so that both factorizations use the same primes. (Note the 5 to the zero power!) Then gcd(85, 289) = 50171 = 17, by choosing the smaller power in each case.

Part a: Use the above technique to find the GCD of the following two numbers, written in their prime factorization: (Note that as above, not every prime already appears as part of each factorization.) 2 3 5 2 111 472 2 1 3 3 5 1 7 5 131 You can write your final answer in factored form. Sometimes instead of the GCD, we want the Least Common Multiple, or LCM, of two numbers. lcm(a, b) is the smallest number which is a multiple of both a and b. (You have used LCMs to find the least common denominators for fractions.) For example, lcm(6, 8) = 24, because 24 is the first number that is a multiple of both 6 and 8: Multiples of 6: 6, 12, 18, 24 , 30, 36, . . . Multiples of 8: 8, 16, 24 , 32, 40, . . . The technique for finding GCDs from the prime factorization can be modified to find the LCM: If a and b are written in prime factorizations with the same primes a = p a1 1 p a2 2 · p an n b = p b1 1 p b2 2 · p bn n 1 2 then lcm(a, b) = p max(a1,b1) 1 p max(a2,b2) 2 . . . pmax(an,bn) n . In other words, do as before, but choose the larger exponent on each prime. For example, 6 = 2 · 3 and 8 = 23 . Writing these using the same primes gives 6 = 21 3 1 8 = 23 3 0 and lcm(6, 8) = 23 3 1 = 24.

Part b: Use the above technique to find the LCM of the numbers given below in their prime factorization (same numbers as before): 2 3 5 2 111 472 2 1 3 3 5 1 7 5 131

Part c: Given the ways above to find the LCM and the GCD, explain why the following relationship holds for any two positive integers a and b: a · b = gcd(a, b) · lcm(a, b). (You don’t have to write a formal proof, but explain why it should hold.)

Part d: The result of Part c above provides a way to find the LCM if we can find the GCD. (Note that we already know an efficient way to compute GCDs!) Suppose that you know that for two numbers a and b, gcd(a, b) = 34, and that a · b = 85, 680. Compute lcm(a, b).

Answer #1

I am giving the solution for part (C) and (D) . Hope it will be helpful .

in part (a) and (b) the number given in prime factorization is not clear to me. It may be for the spacing between them.

Find the optimal strategies and the value of the game. Indicate
whether it is a fair or a strictly determinable game:
b1
b2
b3
b4
a1
2
10
7
0
a2
3
4
9
-1
a3
-6
-3
11
-3
a4
8
5
-4
-5

Below is an example of key generation, encryption, and
decryption using RSA. For the examples below, fill in the
blanks to indicate what each part is or answer the
question.
Public key is (23, 11) What is 23 called?
_______________, What is 11 called?_______________
Private key is (23, 13) What is 23
called?_______________, What is 13
called?_______________
23 can be part of the public key because it is very hard
to _______________ large prime numbers.
ENCRYPT (m) = m^e mod...

discrete mathematics
1. How many element are in A1 È A2 if there are 12 elements A1,
18 elements in A2 and
a) A1 Ç A2 =Æ?
b) | A1 Ç A2 | =1?
c) | A1 Ç A2 | =6?
d) A1 Í A2?
2. There are 345 students at a college who have taken a course
in calculus, 212 who have taken a course in discrete mathematics
and 188 who have taken courses in both calculus and discrete...

A student will randomly select 5 cards from a deck of 52 cards.
Each card is uniquely identified by a label which is a combination
of a letter (one of the following: A, B, C, D) followed by a number
(one of the following: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13).
The labels on the cards are A1, A2, A3, A4, A5, A6, A7, A8, A9,
A10, A11, A12, A13, B1, B2, B3, B4,...

A student will randomly select 5 cards from a deck of 52 cards.
Each card is uniquely identified by a label which is a combination
of a letter (one of the following: A, B, C, D) followed by a number
(one of the following: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13).
The labels on the cards are A1, A2, A3, A4, A5, A6, A7, A8, A9,
A10, A11, A12, A13, B1, B2, B3, B4,...

.A researcher is interested in comparing sunblocks and their
protection level for various skin types. He designed a two-factor
factorial design with Factor A as type of sunblock with 4 levels
and Factor B as skin type with 5 levels. He used 4 replications for
each treatment. The protection level was measured on a scale from 1
to 5 based on the overall amount of sunburn for a 8 square
centimeter patch of skin on the subjects' backs. Based on...

A large collection of one-digit random numbers should have
about 50% odd and 50% even digits\ because five of the ten digits
are odd (1, 3, 5, 7, and 9) and five are even (0, 2, 4, 6,
and 8).A. .Find the proportion of odd-numbered digits in the
following lines from a random number table. Count carefully:
9 9 2 8 9 7 6 5 8 3 0 8 6 0 2
3 7 8 4 9 9 2 8...

You are given a transition matrix P. Find the
steady-state distribution vector. HINT [See Example 4.]
A) P =
5/6
1/6
7/9
2/9
B) P =
1/5
4/5
0
5/8
3/8
0
4/7
0
3/7

A
researcher hypothesizes that caffeine will affect the speed with
which people read, but differently if people get a full night’s
sleep (e.g., 8 hours) than if they do not get a full night’s sleep
(e.g., 2 hours). To test this, the researcher randomly assigns 24
people into one of 6 conditions defined by fully crossing Factor A
and Factor B:
Factor
A: 100 mg Caffeine (a1), 50mg Caffeine (a2) or Placebo (a3) Factor
B: 8 hours of sleep (b1)...

2. How many ways can you select a planning committee of three
for a group of eight executives
3. You have produced four advertisements to use while selling a
new product. What are all the possible ways you can order these
four ads if you plan to only use two during the summer months
4. A manufacturer of cranes purchases electric motors from three
suppliers: General Electric, Westinghouse, and Samsung. Thirty
percent of the motors are purchased from General Electric,...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 12 minutes ago

asked 14 minutes ago

asked 27 minutes ago

asked 30 minutes ago

asked 39 minutes ago

asked 55 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago