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

\[\begin{split} \begin{aligned} A_1(x) &= \{p\in\mathbb{N}:p~\text{is prime},~p\leq x,~\text{and}~p \equiv 1 \bmod 4\}, \\ A_3(x) &= \{p\in\mathbb{N}:p~\text{is prime},~p\leq x,~\text{and}~p \equiv 3 \bmod 4\}, \end{aligned} \end{split}\]

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:

\[\begin{split} \begin{aligned} x^2-1 &= (x-1)(x+1), \\ x^3-1 &= (x-1)(x^2+x+1), \\ x^4-1 &= (x-1)(x+1)(x^2+1). \end{aligned} \end{split}\]

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.