ID # 1226043119 - Written Homework Week #9
pdf
keyboard_arrow_up
School
Arizona State University *
*We aren’t endorsed by this school
Course
MAT 243
Subject
Mathematics
Date
Apr 3, 2024
Type
Pages
5
Uploaded by ChiefTank13657
ID # 1226043119 - Written Homework Week #9 1 1.
True of False? If you think the statement is true, then prove it. If you think the statement is false, then give a counter example. (a)
Assume a /
= 0
, b, c are integers. If a
|
c and b
|
c then ab
|
c
. False. Let a = 3, b = 9, c = 18. Here 3|18 and 9|18. ab = 27. 27 does not divide 18, so the statement is false. (b)
Assume a /
= 0
, b, c are integers. If a
|
b
, then a
|
bc
. True. Given a|b.
b = qa where q is an integer.
bc = qac = q(ac)
a|bc as a, b, c and q are integers. 2.
Use modular arithmetic to find (a)
(177 mod 31 + 270 mod 31) mod 31 = (22 + 22) mod 31 = 13 (b)
an integer a
, such that a mod 47 = 23 and −
47 ≤ a ≤ 0.
a = -24 (c)
(12345678 · 9056348992391) mod 5. Show your work. 12345678 -3 = 12345675 5|12345675
12345678 ≡ 3 (mod 5) 9056348992391 – 1 = 9056348992390 5|9056348992390
9056348992391 ≡ 1 (mod 5) Therefore, 12345678 · 90563489923 ≡ (3 x 1) (mod 5) So, (12345678 · 9056348992391) mod 5 = 3
ID # 1226043119 - Written Homework Week #9 2 (d)
4
123456754
mod 5. Show your work. When n is even, 4
n
≡ 1 (mod 5) When n is odd, 4
n
≡ 4 (mod 5) As 123456754 is even, 4
123456754
≡ 1 (mod 5) Therefore, 4
123456754
mod 5 = 1
3.
(a) Find the smallest positive integer n such that 5
n
mod 7 = 1. 5
6
mod 7 = 1 So, n = 6 (b) Use the previous result, modular arithmetic and laws of exponents from basic algebra to find 5
236
mod 7. Show your work. 5
236
mod 7 = ((5
6
)
39
x 5
2
) mod 7 = 1 x 4 = 4 4.
Convert (12021)
10
to duodecimal (base 12) using repeated application of the division algorithm. Show all your steps. 12021 = 12 (1001) + 9 1001 = 12 (83) + 5 83 = 12 (6) + 11 6 = 12 (0) + 6 Therefore, (12021)
10
= (6B59)
12
5.
Carry out the hexadecimal addition FA1 + 9BC. DO NOT convert the hex numbers to decimal. FA1 +9BC = 195D
ID # 1226043119 - Written Homework Week #9 3 6.
Carry out the binary multiplication 1001 · 1001110101001 efficiently. Show all work. DO NOT convert the binary numbers to decimal. 1001 · 1001110101001 1001110101001 x 1001 ---------------------- 1001110101001 0 0 1001110101001xxx ---------------------- =
1011000011110001
7.
Use fast modular exponentiation to evaluate 7
33554432
mod 11. Show all your steps and take advantage of repetition of remainders. 7
3
≡ 2 mod 11 7
9
≡ 8 mod 11 7
10
≡ (8x7) mod 11 7
10
≡ 1 mod 11 7
33554432
= 7
33554430
x 49 = (7
10
)
3355443
x 49 ≡ (1 x 5) mod 11 Therefore, 7
33554432
mod 11 = 5
8.
Give a formula for the decimal representation of the largest octal number with 50 digits. Show your work. (Hint: Use the formula for the sum of the terms of a geometric sequence.) The decimal representation of x can be x = 7 x (8
0
+ 8
1
+ 8
2
+…+ 8
49
) According to the formula of S
n
X = 7 (8
50
-1) / (8-1) =8
50
-1 Therefore, in decimal form, x = 1.4272477 x 10
45
9.
• Multiply (24306)
7
by (10)
7
. Do not convert to decimals. Generalized the idea for an arbitrary base b > 1. (You don’t have to prove it.)
(243060)
7
• Divide (24306)
7
by (10)
7
. Find the quotient and the remainder. Gen- eralized the idea for an arbitrary base b > 1. (You don’t have to prove it.) Quotient = (2430)
7
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
ID # 1226043119 - Written Homework Week #9 4 Remainder = (6)
7
10.
• Find the number of digits in the binary system of the decimal number 2048.
12
• Find the number of digits in the binary system of the decimal number 2245. 12 • Find the number of digits in the ternary (base 3) system of the decimal number 2245. 8 • Generalize the idea and find a logarithm formula for the number of digits in base b > 1 system of the decimal number 2245. Your formula should be given in terms of b
. (You don’t have to prove it.) In base b, number of digits for 2245 = log
b
(2245) + 1
• Generalize the idea and find a logarithm formula for number of digits in base b > 1 system of the decimal number n > 0. Your formula should be given in terms of b and n
.(You don’t have to prove it.) In base b, number of digits for n = log
b
(n) + 1
11.
Use prime factorization to demonstrate that 621 and 82 are relatively prime to each other. 621 = 3
3
x 23 82 = 2 x 41 As there are no common factors, 621 and 82 are relatively prime. 12.
Use the Euclidean Algorithm to demonstrate that 621 and 82 are relatively prime to each other. 621 = 82 x 7 + 47 82 = 47 x 1 + 35 47 = 35 x 1 + 12 35 = 12 x 2 + 11 12 = 11 x 1 + 1 11 = 1 x 11 + 0 As the last non-zero remainder is 1, the gcd of 621 and 82 is 1. Therefore, they are relatively prime to each other. 13.
The numbers 2221
, 2237
, 2239
, 2243 are prime. Use the Fundamental The- orem of Arithmetic and explain why 2221 · 2243 and 2237 · 2239 cannot be equal. If 2221 · 2243 = 2237 · 2239 The prime factors of both sides would have to be the same. Since 2221, 2243, 2237 and 2239 are all prime numbers, the terms are both different.
ID # 1226043119 - Written Homework Week #9 5 14.
Suppose p and q are distinct primes. List all the positive divisors of p
2
q
3
. How many divisors of this number have? Can you find the general formula for the number of divisors of a positive integer in the form of p
a
· q
b
where a, b are non-negative integers? Explain it briefly. The positive divisors of p
2
q
3
are 1,p,q,p
2
,q
2
,q
3
,pq ,pq
2
,pq
3
,
p
2
q
,p
2
q
2
,p
2
q
3
So there are 12
divisors. For a positive integer p
a
· q
b
the number of divisors = (a+1)(b+1)