Deck 4: A: Number Theory and Cryptography

Question 1

Find the prime factorization of 45,617.

Answer 1

7 · 13 · 97

Question 2

suppose that a and b are integers, a ≡ 4 (mod 7), and b ≡ 6 (mod 7). Find the integer c with 0 ≤ c ≤ 6
such that

Answer 2

4

Question 3

What does a 60-second stop watch read 82 seconds after it reads 27 seconds?

Answer 3

49 seconds

Question 4

Prove or disprove: For all integers

Question 5

Prove or disprove: For all integers

Question 6

Find the prime factorization of 1,025.

Question 7

Find the prime factorization of 8,827.

Question 8

suppose that a and b are integers, a ≡ 4 (mod 7), and b ≡ 6 (mod 7). Find the integer c with 0 ≤ c ≤ 6
such that

Question 9

Find the prime factorization of 510,510.

Question 10

Find the prime factorization of 1,024.

Question 11

List all positive integers less than 30 that are relatively prime to 20.

Question 12

suppose that a and b are integers, a ≡ 4 (mod 7), and b ≡ 6 (mod 7). Find the integer c with 0 ≤ c ≤ 6
such that

Question 13

Find the prime factorization of 111,111.

Question 14

Prove or disprove: For all integers

Question 15

Prove or disprove: For all integers

Question 16

Prove or disprove: For all integers

Question 17

Prove or disprove: For all integers

Question 18

What does a 60-second stop watch read 54 seconds before it reads 19 seconds?

Question 19

Prove or disprove: For all integers

Question 20

suppose that a and b are integers, a ≡ 4 (mod 7), and b ≡ 6 (mod 7). Find the integer c with 0 ≤ c ≤ 6
such that

Question 21

Find the hexadecimal expansion of (ABC)16+(2F5)16.

Question 22

Find gcd(2 by directly finding the largest divisor of both numbers.

Question 23

Prove or disprove:

Question 24

Prove or disprove: The sum of two primes is a prime.

Question 25

Find 289 mod 17.

Question 26

Find lcm by directly finding the smallest positive multiple of both numbers.

Question 27

Prove or disprove:
If f(n)=n²-n+17, then f(n) is prime for all positive integers n.

Question 28

Find 18 mod 7.

Question 29

Find −88 mod 13.

Question 30

Prove or disprove: There exist two consecutive primes, each greater than 2.

Question 31

Find 50! mod 50.

Question 32

Prove or disprove: A positive integer congruent to 1 modulo 4 cannot have a prime factor congruent to 3 modulo 4.

Question 33

Prove or disprove: If p and q are primes then p + q is composite.

Question 34

Find lcm by directly finding the smallest positive multiple of both numbers.

Question 35

Find 50! mod 49!.

Question 36

Find by directly finding the largest divisor of both numbers.

Question 37

Prove or disprove:

Question 38

Prove or disprove: The sum of two irrational numbers is irrational.

Question 39

Suppose that the lcm of two numbers is 400 and their gcd is 10. If one of the numbers is 50, find the other number.

Question 40

Applying the division algorithm with a = −41 and d = 6 yields what value of r?

Question 41

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 42

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 43

Find an integer a such that

Question 44

Find the integer a such that

Question 45

Find the integer a such that

Question 46

Find integers a and b such that

Question 47

In 53-56 find each of these values

Question 48

In 53-56 find each of these values

Question 49

Find the smallest integer

Question 50

Find a div m and a mod m when

Question 51

In 53-56 find each of these values
(123 mod 19 + 342 mod 19) mod 19

Question 52

Find a div m and a mod m when

Question 53

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 54

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 55

Show that if a, b, k and m are integers such that (mod m).

Question 56

Find four integers b (two negative and two positive) such that 7 ≡ b (mod 4).

Question 57

Find three integers m such that 13 ≡ 7 (mod m).

Question 58

In 53-56 find each of these values
(123 mod 19 · 342 mod 19) mod 19

Question 59

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 60

Find a div m and a mod m when

Question 61

Explain in words the difference between and

Question 62

In 82-83 find the sum and product of each of these pairs of numbers. Express your answer as a binary expansion.

Question 63

What sequence of pseudorandom numbers is generated using the pure multiplicative generator = mod 11 with seed =2 ?

Question 64

Convert (11010111100)₂ to base 8 .

Question 65

Convert (204)₁₀ to base 2 .

Question 66

Convert (10,000)₁₀ to base 2 .

Question 67

Convert (11101)₂ to base 16 .

Question 68

(a) Find two positive integers, each with exactly three positive integer factors greater than 1. (b) Prove that there are an infinite number of positive integers, each with exactly three positive integer factors greater than 1.

Question 69

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 70

Convert (101011)₂ to base 8 .

Question 71

Convert (2AC)₁₆ to base 10 .

Question 72

In questions 58-64 determine whether each of the following "theorems" is true or false. Assume that a, b, c, d,
and m are integers with m > 1.

Question 73

Convert (271)₈ to base 2 .

Question 74

Prove or disprove: if p and q are prime numbers, then pq+1 is prime.

Question 75

Either find an integer such that (mod 6) and (mod 9) are both true, or else prove that there is no such integer.

Question 76

Convert (1 1101)₂ to base 10 .

Question 77

Convert (10011000011)₂ to base 16 .

Question 78

Convert (6253)₈ to base 2 .

Question 79

Convert (BC1)₁₆ to base 2 .

Question 80

Convert (8091)₁₀ to base 2 .