#number-theory

Start with any positive integer $n$. If $n$ is even, replace it by $n/2$, and if $n$ is odd, replace it by $3n+1$. Repeat this forever. Prove or disprove that every starting value eventually reaches 1.

Twin primes are pairs of primes that differ by 2, such as $11,13$ or $41,43$. Prove that there are infinitely many twin prime pairs.

Prove that every even integer greater than 2 is the sum of two primes. For example $28=5+23$ and $100=3+97$.

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$. Prove that $\frac{a^2+b^2}{ab+1}$ is the square of an integer.

$n$ runners start together on a circular track of length 1 and run forever, each at its own constant speed, with all speeds different. Prove that for each runner there is a moment when every other runner is at distance at least $1/n$ along the track. The speeds $0,1,\dots ,n-1$ show that $1/n$…

Given an integer $N$ with $b$ bits, find its prime factorization. Is there a classical (non-quantum) algorithm that does this in time polynomial in $b$?

Find a rectangular box whose three edges, three face diagonals and space diagonal all have integer lengths, or prove that none exists. In other words, find positive integers $a,b,c$ such that $a^2+b^2$, $b^2+c^2$, $a^2+c^2$ and $a^2+b^2+c^2$ are all perfect squares.

Prove that for every integer $n\ge 2$ there are positive integers $x,y,z$ with $\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}.$

A positive integer is perfect if it equals the sum of its proper divisors, like $6=1+2+3$ and $28=1+2+4+7+14$. Every known perfect number is even. Is there an odd perfect number?

Euler's totient $\phi (n)$ counts the integers in $1,\dots ,n$ that are coprime to $n$. When $n$ is prime, $\phi (n)=n-1$, which certainly divides $n-1$. Is there a composite number $n$ for which $\phi (n)$ divides $n-1$?

The Riemann zeta function is defined by $\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$ for $\mathrm{Re}(s)>1$ and extended by analytic continuation to all complex $s\ne 1$. It vanishes at $s=-2,-4,-6,\dots$. Prove that every other zero of $\zeta$ has real part exactly $1/2$.

Give a deterministic algorithm that decides whether an integer $n$ is prime in time polynomial in the number of digits of $n$, without relying on any unproved conjecture.

Prove that for every positive integer $n$ there is a prime number strictly between $n^2$ and $(n+1{)}^2$.

Is there an algorithm that takes any polynomial equation with integer coefficients, in any number of unknowns, and decides whether it has a solution in integers?

Let $N(a)$ be the number of times the integer $a>1$ appears in Pascal's triangle. For example, $N(3003)=8$. Is there a constant $M$ with $N(a)\le M$ for every $a>1$?

Prove that the equation $a^n+b^n=c^n$ has no solution in positive integers $a,b,c$ when $n$ is an integer greater than 2.

The numbers $8=2^3$ and $9=3^2$ are consecutive perfect powers. Prove that they are the only such pair, that is, the only solution of $x^a-y^b=1$ in integers $x,y,a,b>1$ is $3^2-2^3=1$.

Let $x_1,x_2,x_3,\dots$ be any infinite sequence with every $x_i$ equal to $+1$ or $-1$. Prove that for every $C$ there are positive integers $k$ and $d$ with $\left|{\sum }_{i=1}^k{x}_{id}\right|>C.$

Find the exact value of ${\sum }_{n=1}^{\infty }\frac{1}{n^2}=1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\cdots$ and prove that your answer is correct.