Exercises¶
Problem 1
Disprove: If \(p\in\mathbb{N}\), then \((x+1)^p-(x-1)^p = 2p x^{p-1}\) for all \(x\in\mathbb{R}\).
Write a function named symmetric_power() that accepts a positive integer \(p\in\mathbb{N}\).
Return True if \((x+1)^p-(x-1)^p = 2p x^{p-1}\) for all \(x\in\mathbb{R}\) and False otherwise.
Use symmetric_power() to find the smallest counterexample, meaning the smallest \(p_0\) such that \((x+1)^{p_0}-(x-1)^{p_0} \neq 2p_0 x^{p_0-1}\), by checking \(p = 1,2,\ldots\) until symmetric_power(p) returns False.
Store the value of \(p_0\) as the variable problem1_counterexample.
Problem 2
In 1772, Euler discovered a polynomial that seems to produce prime numbers for each natural number input.
Disprove: For every nonnegative integer \(k\), the number \(k^2 + k + 41\) is prime.
Write a function named eulerpoly() that accepts a nonnegative integer \(k\).
Return True if \(k^2 + k + 41\) is prime and False otherwise.
Use eulerpoly() to find the smallest counterexample, that is, \(k_0\) such that \(k_0^2 + k_0 + 41\) is composite.
Store the value of \(k_0\) as the variable problem2_counterexample.
Problem 3
Numbers of the form \(2^{2^k}+1\), for \(k = 0, 1, 2, \ldots\), are called Fermat numbers. The first few are \(3\), \(5\), and \(17\).
Disprove: For every nonnegative integer \(k\), the Fermat number \(2^{2^k}+1\) is prime.
Write a function named fermat() that accepts a nonnegative integer \(k\).
Return True if the Fermat number \(2^{2^k}+1\) is prime and False otherwise.
Use fermat() to find the smallest counterexample, that is, \(k_0\) such that \(2^{2^{k_0}}+1\) is composite.
Store the value of \(k_0\) as the variable problem3_counterexample.
Problem 4
Numbers of the form \(2^p - 1\) where \(p\in\mathbb{N}\) are called Mersenne numbers, and a Mersenne number that is prime is called a Mersenne prime.
Disprove: For every prime number \(p\), the Mersenne number \(2^p-1\) is also prime.
Write a function named mersenne() that accepts a prime number \(p\).
Return True if \(2^p-1\) is prime and False otherwise.
Use mersenne() to find the smallest counterexample, that is, \(p_0\) such that \(2^{p_0}-1\) is composite and \(p_0\) is prime.
Store the value of \(p_0\) as the variable problem4_counterexample.
Problem 5
Every prime number larger than \(2\) is odd, so it is congruent to either \(1\) or \(3\) modulo \(4\). Let \(\pi_1(x)\) denote the number of primes that are less than or equal to \(x\) and congruent to \(1\) modulo \(4\), and define \(\pi_3(x)\) likewise. That is, if
then \(\pi_1(x) = |A_1(x)|\) and \(\pi_3(x) = |A_3(x)|\). For example, \(A_1(15) = \{5,13\}\) and \(A_3(15) = \{3, 7, 11\}\), so \(\pi_1(15) = 2\) and \(\pi_3(15) = 3\).
Is \(\pi_1(x)\) or \(\pi_3(x)\) bigger? This problem is called a “prime number race.”
Disprove: \(\pi_3(x) \geq \pi_1(x)\) for all integers \(x \geq 3\).
Write a function named prime_race() that accepts an integer \(x \geq 3\).
Return \(\pi_1(x)\) and \(\pi_3(x)\).
Use prime_race() to find the smallest counterexample, that is, the smallest integer \(x\) such that \(\pi_3(x) < \pi_1(x)\).
Store the value of \(x\) as the variable problem5_counterexample.
Hint: Only prime values of \(x\) need to be checked (can you explain why?).
Test Cases
print(prime_race(15))
print(prime_race(100))
(2, 3)
(11, 13)
Problem 6
Factoring \(x^n - 1\) over the integers seems to produce a pattern:
Irreducible integer-coefficient polynomial factors of \(x^n - 1\), such as \((x-1)\), \((x+1)\), \((x^2+1)\), and \((x^2+x+1)\), are called cyclotomic polynomials. Writing these polynomials as \(c_2 x^2 + c_1 x + c_0\), in each case the coefficients \(c_2,c_1,c_0\) are in \(\{-1,0,1\}\) (unlike, for example, \(2x + 1\), which has a coefficient \(c_1 = 2\)).
Disprove: For every positive integer \(n\in\mathbb{N}\), every coefficient of every cyclotomic polynomial that is a factor of \(x^n - 1\) is in the set \(\{1,0,-1\}\).
Write a function named cyclotomic() that accepts a positive integer \(n\in\mathbb{N}\).
Find the distinct coefficients that appear in the irreducible factors of \(x^n - 1\).
Return True if all coefficients are in \(\{-1,0,1\}\); return False otherwise.
Use cyclotomic() to find the smallest counterexample.
That is, find \(n_0\) such that \(x^{n_0} - 1\) has a cyclotomic polynomial factor with a coefficient not in \(\{-1,0,1\}\).
Store the value of \(n_0\) as the variable problem6_counterexample.