Unit 2: Number Theory-II - Practice Quiz

1 Which of the following is the definition of a prime number?

2 Which of the following numbers is not prime?

3 What is the smallest prime number?

4 The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written as a product of primes that is unique up to what?

5 What is the prime factorization of ?

6 Which of these represents a valid prime factorization?

7 When using trial division to test whether is prime, up to which value must you test divisors?

8 Using trial division, which is the first prime you would test to check if is prime?

9 Trial division determines primality by checking whether is divisible by any:

10 The Sieve of Eratosthenes is an algorithm used to:

11 In the Sieve of Eratosthenes, after selecting the prime , what do you do next?

12 When applying the Sieve of Eratosthenes up to , once you finish with the prime , what is the next prime to sieve with?

13 The Prime Number Theorem approximates the number of primes less than by which expression?

14 The Prime Number Theorem tells us that as numbers grow larger, primes become:

15 What is ?

16 What is ?

17 For positive integers and , which relationship always holds?

18 Two integers whose greatest common divisor is are called:

19 The Euclidean algorithm computes by repeatedly replacing the pair with:

20 Using the Euclidean algorithm, what is ?

21 What is the prime factorization of ?

22 Using the Euclidean algorithm, what is ?

23 If and , what is the product ?

24 Which pair of integers satisfies ?

25 To test whether is prime using trial division, up to which integer must you test divisors?

26 When applying the sieve of Eratosthenes to find all primes up to , what is the largest prime whose multiples must be crossed out?

27 Which of the following numbers is prime?

28 What is ?

29 According to the prime number theorem, the number of primes less than is approximately:

30 How many division steps does the Euclidean algorithm take to compute ?

31 How many positive divisors does have?

32 The equation has integer solutions if and only if is a multiple of which value?

33 Two primes and are called twin primes if they differ by . Which of the following is a twin prime pair?

34 If , the integers and are said to be:

35 Using trial division, which is the smallest prime factor of ?

36 What is computed by the Euclidean algorithm?

37 Which statement correctly describes the fundamental theorem of arithmetic?

38 How many primes are there less than or equal to ?

39 Given that , which expression correctly writes as a linear combination?

40 Using the prime number theorem approximation , roughly how many primes are less than ? (Use .)

41 Let . How many positive divisors of are perfect squares?

42 If and , and with both having exactly the same set of prime factors as , how many ordered pairs with are possible?

43 How many division steps does the Euclidean algorithm take to compute ?

44 Find integers with where . What is ?

45 When testing whether is prime by trial division, what is the largest prime you must test as a potential divisor?

46 In the sieve of Eratosthenes applied to integers up to , when crossing out multiples of the prime , what is the first (smallest) number that gets crossed out at this step?

47 By the prime number theorem, the density of primes near a large integer is approximately . Roughly how many times denser are primes near compared to near ?

48 Which of the following statements about twin primes and the number for a prime is always true?

49 The number of trailing zeros of in base is determined by the exponent of which prime in its factorization?

50 For positive integers , which identity always holds?

51 For which values of does the equation have integer solutions?

52 Using the Euclidean algorithm, what is ?

53 Which of these Mersenne-type numbers is NOT prime, illustrating that prime does not guarantee prime?

54 How many positive integers are 'squarefree' (not divisible by any perfect square greater than )?

55 To find all primes up to using the sieve of Eratosthenes, up to which value must you sieve (use primes as strike-out bases)?

56 The prime number theorem states . Which refinement gives a more accurate approximation for finite ?

57 If and , and , which single value of is consistent with and ?

58 Given expressed as , the complete set of solutions to is described by which formula (with )?

59 The number of steps in the Euclidean algorithm for with is maximized (relative to size) when are consecutive terms of which sequence?

60 By a classic result, how many primes are there of the form less than or equal to a given bound, in the limit?