Scribd
Upload
47 views

Chapter 3. The Fundamentals: Algorithms The Integers: Please Write Your Name

This document contains a multi-part mathematics assignment involving integers, divisibility, modular arithmetic, binary, octal and base-3 number systems, prime numbers, the Euclidean algorithm, and finding the greatest common divisor. The assignment includes tasks like determining whether numbers are divisible by other numbers, finding remainders and quotients, solving congruences, converting between number bases, performing arithmetic in different bases, factorizing numbers, and checking for relative primality.

Uploaded by

Quang Nguyen
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
47 views

Chapter 3. The Fundamentals: Algorithms The Integers: Please Write Your Name

This document contains a multi-part mathematics assignment involving integers, divisibility, modular arithmetic, binary, octal and base-3 number systems, prime numbers, the Euclidean algorithm, and finding the greatest common divisor. The assignment includes tasks like determining whether numbers are divisible by other numbers, finding remainders and quotients, solving congruences, converting between number bases, performing arithmetic in different bases, factorizing numbers, and checking for relative primality.

Uploaded by

Quang Nguyen
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Please write your name

Name: . . . . . . . . . . . .
Class: . . . . . . . . . . . .

Chapter 3. The Fundamentals: Algorithms The


Integers
1. Does 17 divide each of these numbers?

a) 68 b) 84 c) 357 d) 1001

2. Suppose that a and b are integers, a ≡ 4 (mod 13), and b ≡ 9 (mod13). Find the
integer c with 0 ≤ c ≤ 12 such that

a) c ≡ 9a (mod 13). c) c ≡ a + b (mod 13). e) c ≡ a2 + b2 (mod 13).


b) c ≡ 11b (mod 13). d) c ≡ 2a + 3b (mod 13). f) c ≡ a3 − b3 (mod 13).

3. Find a div m and a mod m when

a) a = 144, m = 7. c) a = 199, m = 19. e) a = −111, m = 99


b) a = −17, m = 2. d) a = −221, m = 23. f) a = −9999, m = 101.

4. Find counterexamples to each of these statements about congruences.

a) If ac ≡ bc (mod m), where a, b, c, and m are integers with m ≥ 2, then a ≡ b (mod


m).

b) If a ≡ b (mod m) and c ≡ d (mod m), where a, b, c, d, and m are integers with c


and d positive and m ≥ 2, then ac ≡ bd (mod m) .

5. Find the integer a such that

a) a ≡ 43( mod 23) and −22 ≤ a ≤ 0 c) a ≡ −11 (mod 21) and 90 ≤ a ≤ 110.
b) a ≡ 17 (mod 29) and −14 ≤ a ≤ 14

6. Find the integer a such that

a) a ≡ −15(mod 27) and −26 ≤ a ≤ 0. c) a ≡ 99 (mod 41) and 100 ≤ a ≤ 140


b) a ≡ 24 (mod 31) and −15 ≤ a ≤ 15.

7. List five integers that are congruent to 4 modulo 12 .

8. Convert the decimal expansion of each of these integers to a binary expansion.

a) 231 b) 4532 c) 97644

9. Convert the binary expansion of each of these integers to a decimal expansion

Page 1
a) (1 1111)2 b) (10 0000 0001)2

10. Find the sum and the product of each of these pairs of numbers. Express your
answers as a binary expansion.

a) (100 0111)2 , (111 0111)2 c) (10 1010 1010)2 , (1 1111 0000)2


b) (1110 1111)2 , (1011 1101)2 d) (10 0000 0001)2 , (11 1111 1111)2

11. Find the sum and product of each of these pairs of numbers. Express your
answers as a base 3 expansion.

a) (112)3 , (210)3 c) (20001)3 , (1111)3


b) (2112)3 , (12021)3 d) (120021)3 , (2002)3

12. Find the sum and product of each of these pairs of numbers. Express your
answers as an octal expansion.

a) (763)8 , (147)8 c) (1111)8 , (777)8


b) (6001)8 , (272)8 d) (54321)8 , (3456)8

13. Determine whether each of these integers is prime.

a) 21 b) 29 c) 71 d) 97 e) 111 f) 143

14. Use the Euclidean algorithm to find

a) gcd(1, 5). c) gcd(1529, 14038). e) gcd(1529, 14039).


b) gcd(123, 277). d) gcd(100, 101). f) gcd(11111, 111111).

15. Find the prime factorization of each of these integers.

a) 39 b) 81 c) 143 d) 289 e) 101 f) 899

16. Determine whether the integers in each of these sets are pairwise relatively
prime.

a) 21, 34, 55 c) 25,41,49,64


b) 14, 17, 85 d) 17,18,19,23

Page 2

You might also like