Putnam Archive — Number Theory

Let $m_0$ and $n_0$ be distinct positive integers. For every positive integer $k$, define $m_k$ and $n_k$ to be the relatively prime positive integers such that $$\frac{m_k}{n_k} = \frac{2m_{k-1} + 1}{2n_{k-1}+1}.$$ Prove that $2m_k+1$ and $2n_k+1$ are relatively prime for all but finitely many positive integers $k$.

Let $b_0 = 0$ and, for $n \geq 0$, define $b_{n+1} = 2b_n^2 + b_n + 1$. For each $k \geq 1$, show that $b_{2^{k+1}} - 2b_{2^k}$ is divisible by $2^{2k+2}$ but not by $2^{2k+3}$.

Suppose $S$ is a nonempty set of positive integers with the property that if $n$ is in $S$, then every positive divisor of $2025^n -15^n$ is in $S$. Must $S$ contain all positive integers?

Let $p$ be a prime number greater than $3$. For each $k \in \{1,\dots,p-1\}$, let $I(k) \in \{1,2,\dots,p-1\}$ be such that $k \cdot I(k) \equiv 1 \pmod{p}$. Prove that the number of integers $k \in \{1,\dots,p-2\}$ such that $I(k+1) < I(k)$ is greater than $p/4-1$.

Let $\mathbb{N} = \{1,2,3,\dots\}$. Find the largest real constant $r$ such that there exists a function $g\colon \mathbb{N} \to \mathbb{N}$ such that $$g(n+1)-g(n) \geq (g(g(n)))^r$$ for all $n \in \mathbb{N}$.

Determine all positive integers $n$ for which there exist positive integers $a$, $b$, and $c$ satisfying $$2a^n + 3b^n = 4c^n.$$

Find all primes $p > 5$ for which there exists an integer $a$ and an integer $r$ satisfying $1 \leq r \leq p-1$ with the following property: the sequence $1,a,a^2,\dots,a^{p-5}$ can be rearranged to form a sequence $b_0,b_1,b_2,\dots,b_{p-5}$ such that $b_n-b_{n-1}-r$ is divisible by $p$ for $1 \leq n \leq p-5$.

Let $n$ and $k$ be positive integers. The square in the $i$th row and $j$th column of an $n$-by-$n$ grid contains the number $i+j-k$. For which $n$ and $k$ is it possible to select $n$ squares from the grid, no two in the same row or column, such that the numbers contained in the selected squares are exactly $1,2,\dots,n$?

For a nonnegative integer $k$, let $f(k)$ be the number of ones in the base 3 representation of $k$. Find all complex numbers $z$ such that $$\sum_{k=0}^{3^{1010}-1} (-2)^{f(k)} (z+k)^{2023} = 0.$$

For each positive integer $n$, let $k(n)$ be the number of ones in the binary representation of $2023 \cdot n$. What is the minimum value of $k(n)$?

Determine which positive integers $n$ have the following property: For all integers $m$ that are relatively prime to $n$, there exists a permutation $\pi\colon \{1,2,\dots,n\} \to \{1,2,\dots,n\}$ such that $\pi(\pi(k)) \equiv mk \pmod{n}$ for all $k \in \{1,2,\dots,n\}$.

Let $n$ be a positive integer. For $i$ and $j$ in $\{1,2,\dots,n\}$, let $s(i,j)$ be the number of pairs $(a,b)$ of nonnegative integers satisfying $ai +bj=n$. Let $S$ be the $n$-by-$n$ matrix whose $(i,j)$ entry is $s(i,j)$. For example, when $n=5$, we have $S = \begin{bmatrix} 6 & 3 & 2 & 2 & 2 \\ 3 & 0 & 1 & 0 & 1 \\ 2 & 1 & 0 & 0 & 1 \\ 2 & 0 & 0 & 0 & 1 \\ 2 & 1 & 1 & 1 & 2 \end{bmatrix}$. Compute the determinant of $S$.

Let $p$ be a prime number greater than 5. Let $f(p)$ denote the number of infinite sequences $a_1, a_2, a_3, \dots$ such that $a_n \in \{1, 2, \dots, p-1\}$ and $a_n a_{n+2} \equiv 1 + a_{n+1} \pmod{p}$ for all $n \geq 1$. Prove that $f(p)$ is congruent to 0 or 2 $\pmod{5}$.

Suppose that $P(x) = a_1 x + a_2 x^2 + \cdots + a_n x^n$ is a polynomial with integer coefficients, with $a_1$ odd. Suppose that $e^{P(x)} = b_0 + b_1 x + b_2 x^2 + \cdots$ for all $x$. Prove that $b_k$ is nonzero for all $k \geq 0$.

Assign to each positive real number a color, either red or blue. Let $D$ be the set of all distances $d > 0$ such that there are two points of the same color at distance $d$ apart. Recolor the positive reals so that the numbers in $D$ are red and the numbers not in $D$ are blue. If we iterate this recoloring process, will we always end up with all the numbers red after a finite number of steps?

For $0 \leq p \leq 1/2$, let $X_1, X_2, \dots$ be independent random variables such that $$X_i = \begin{cases} 1 & \mbox{with probability $p$,} \\ -1 & \mbox{with probability $p$,} \\ 0 & \mbox{with probability $1-2p$,} \end{cases}$$ for all $i \geq 1$. Given a positive integer $n$ and integers $b, a_1, \dots, a_n$, let $P(b, a_1, \dots, a_n)$ denote the probability that $a_1 X_1 + \cdots + a_n X_n = b$. For which values of $p$ is it the case that $$P(0, a_1, \dots, a_n) \geq P(b, a_1, \dots, a_n)$$ for all positive integers $n$ and all integers $b, a_1, \dots, a_n$?

A grasshopper starts at the origin in the coordinate plane and makes a sequence of hops. Each hop has length $5$, and after each hop the grasshopper is at a point whose coordinates are both integers; thus, there are $12$ possible locations for the grasshopper after the first hop. What is the smallest number of hops needed for the grasshopper to reach the point $(2021, 2021)$?

Determine all positive integers $N$ for which the sphere $$x^2 + y^2 + z^2 = N$$ has an inscribed regular tetrahedron whose vertices have integer coordinates.

Let $A$ be the set of all integers $n$ such that $1 \leq n \leq 2021$ and $\gcd(n, 2021) = 1$. For every nonnegative integer $j$, let $$S(j) = \sum_{n \in A} n^j.$$ Determine all values of $j$ such that $S(j)$ is a multiple of 2021.

Let $P(x)$ be a polynomial whose coefficients are all either $0$ or $1$. Suppose that $P(x)$ can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that $P(2)$ is a composite integer?

Let $F_0, F_1, \dots$ be the sequence of Fibonacci numbers, with $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. For $m > 2$, let $R_m$ be the remainder when the product $\prod_{k=1}^{F_m-1} k^k$ is divided by $F_m$. Prove that $R_m$ is also a Fibonacci number.

Say that an $n$-by-$n$ matrix $A = (a_{ij})_{1 \leq i,j \leq n}$ with integer entries is very odd if, for every nonempty subset $S$ of $\{1,2,\dots,n\}$, the $|S|$-by-$|S|$ submatrix $(a_{ij})_{i,j \in S}$ has odd determinant. Prove that if $A$ is very odd, then $A^k$ is very odd for every $k \geq 1$.

How many positive integers $N$ satisfy all of the following three conditions?

1. (i)
   $N$ is divisible by 2020.
2. (ii)
   $N$ has at most 2020 decimal digits.
3. (iii)
   The decimal digits of $N$ are a string of consecutive ones followed by a string of consecutive zeros.

Let $a_n$ be the number of sets $S$ of positive integers for which $$\sum_{k \in S} F_k = n,$$ where the Fibonacci sequence $(F_k)_{k \geq 1}$ satisfies $F_{k+2} = F_{k+1} + F_k$ and begins $F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3$. Find the largest integer $n$ such that $a_n = 2020$.

For a positive integer $n$, define $d(n)$ to be the sum of the digits of $n$ when written in binary (for example, $d(13) = 1+1+0+1=3)$. Let $$S = \sum_{k=1}^{2020} (-1)^{d(k)} k^3.$$ Determine $S$ modulo 2020.

Let $n$ be a positive integer. Prove that $$\sum_{k=1}^n (-1)^{\lfloor k(\sqrt{2}-1) \rfloor} \geq 0.$$ (As usual, $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.)

Determine all possible values of the expression $$A^3+B^3+C^3-3ABC$$ where $A, B$, and $C$ are nonnegative integers.

Let $p$ be an odd prime number, and let $\mathbb{F}_p$ denote the field of integers modulo $p$. Let $\mathbb{F}_p[x]$ be the ring of polynomials over $\mathbb{F}_p$, and let $q(x) \in \mathbb{F}_p[x]$ be given by $$q(x) = \sum_{k=1}^{p-1} a_k x^k,$$ where $$a_k = k^{(p-1)/2} \mod{p}.$$ Find the greatest nonnegative integer $n$ such that $(x-1)^n$ divides $q(x)$ in $\mathbb{F}_p[x]$.

Let $F_m$ be the $m$th Fibonacci number, defined by $F_1 = F_2 = 1$ and $F_m = F_{m-1} + F_{m-2}$ for all $m \geq 3$. Let $p(x)$ be the polynomial of degree $1008$ such that $p(2n+1) = F_{2n+1}$ for $n=0,1,2,\dots,1008$. Find integers $j$ and $k$ such that $p(2019) = F_j - F_k$.

Find all ordered pairs $(a,b)$ of positive integers for which $$\frac{1}{a} + \frac{1}{b} = \frac{3}{2018}.$$

Let $m$ and $n$ be positive integers with $\gcd(m,n) = 1$, and let $$a_k = \left\lfloor \frac{mk}{n} \right\rfloor - \left\lfloor \frac{m(k-1)}{n} \right\rfloor$$ for $k=1,2,\dots,n$. Suppose that $g$ and $h$ are elements in a group $G$ and that $$gh^{a_1} gh^{a_2} \cdots gh^{a_n} = e,$$ where $e$ is the identity element. Show that $gh= hg$. (As usual, $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.)

Suppose that $A,B,C,$ and $D$ are distinct points, no three of which lie on a line, in the Euclidean plane. Show that if the squares of the lengths of the line segments $AB$, $AC$, $AD$, $BC$, $BD$, and $CD$ are rational numbers, then the quotient $$\frac{\mathrm{area}(\triangle ABC)}{\mathrm{area}(\triangle ABD)}$$ is a rational number.

Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n-1$, and $n-2$ divides $2^n - 2$.

Given a real number $a$, we define a sequence by $x_0 = 1$, $x_1 = x_2 = a$, and $x_{n+1} = 2x_n x_{n-1} - x_{n-2}$ for $n \geq 2$. Prove that if $x_n = 0$ for some $n$, then the sequence is periodic.

Let $S$ be the smallest set of positive integers such that

1. (a)
   $2$ is in $S$,
2. (b)
   $n$ is in $S$ whenever $n^2$ is in $S$, and
3. (c)
   $(n+5)^2$ is in $S$ whenever $n$ is in $S$.

Which positive integers are not in $S$?

(The set $S$ is “smallest” in the sense that $S$ is contained in any other such set.)

Suppose that a positive integer $N$ can be expressed as the sum of $k$ consecutive positive integers $$N = a + (a+1) +(a+2) + \cdots + (a+k-1)$$ for $k=2017$ but for no other values of $k>1$. Considering all positive integers $N$ with this property, what is the smallest positive integer $a$ that occurs in any of these expressions?

Suppose that $f(x) = \sum_{i=0}^\infty c_i x^i$ is a power series for which each coefficient $c_i$ is $0$ or $1$. Show that if $f(2/3) = 3/2$, then $f(1/2)$ must be irrational.

Find the number of ordered $64$-tuples $(x_0,x_1,\dots,x_{63})$ such that $x_0,x_1,\dots,x_{63}$ are distinct elements of $\{1,2,\dots,2017\}$ and $$x_0 + x_1 + 2x_2 + 3x_3 + \cdots + 63 x_{63}$$ is divisible by 2017.

Find the smallest positive integer $j$ such that for every polynomial $p(x)$ with integer coefficients and for every integer $k$, the integer $$p^{(j)}(k) = \left. \frac{d^j}{dx^j} p(x) \right|_{x=k}$$ (the $j$-th derivative of $p(x)$ at $k$) is divisible by 2016.

Define a positive integer $n$ to be squarish if either $n$ is itself a perfect square or the distance from $n$ to the nearest perfect square is a perfect square. For example, 2016 is squarish, because the nearest perfect square to 2016 is $45^2 = 2025$ and $2025-2016=9$ is a perfect square. (Of the positive integers between 1 and 10, only 6 and 7 are not squarish.)

For a positive integer $N$, let $S(N)$ be the number of squarish integers between 1 and $N$, inclusive. Find positive constants $\alpha$ and $\beta$ such that $$\lim_{N \to \infty} \frac{S(N)}{N^\alpha} = \beta,$$ or show that no such constants exist.

Evaluate $$\sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} \sum_{n=0}^\infty \frac{1}{k2^n + 1}.$$

Let $a_0=1$, $a_1=2$, and $a_n=4a_{n-1}-a_{n-2}$ for $n\geq 2$. Find an odd prime factor of $a_{2015}$.

Compute $$\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right)$$ Here $i$ is the imaginary unit (that is, $i^2=-1$).

For each real number $x$, let $$f(x) = \sum_{n\in S_x} \frac{1}{2^n},$$ where $S_x$ is the set of positive integers $n$ for which $\lfloor nx \rfloor$ is even. What is the largest real number $L$ such that $f(x) \geq L$ for all $x \in [0,1)$? (As usual, $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$.)

Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0 < a < q/4$ and $\gcd(a,q) = 1$. Show that $N_q$ is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime congruent to $5$ or $7$ modulo $8$.

Given a list of the positive integers $1,2,3,4,\dots$, take the first three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list. Repeat with the three smallest remaining numbers $4,5,7$ and their sum $16$. Continue in this way, crossing off the three smallest remaining numbers and their sum, and consider the sequence of sums produced: $6, 16, 27, 36, \dots$. Prove or disprove that there is some number in the sequence whose base 10 representation ends with $2015$.

\,

For each positive integer $k$, let $A(k)$ be the number of odd divisors of $k$ in the interval $[1, \sqrt{2k})$. Evaluate $$\sum_{k=1}^\infty (-1)^{k-1} \frac{A(k)}{k}.$$

Prove that every nonzero coefficient of the Taylor series of $$(1 - x + x^2)e^x$$ about $x=0$ is a rational number whose numerator (in lowest terms) is either $1$ or a prime number.

A base $10$ over-expansion of a positive integer $N$ is an expression of the form $$N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0$$ with $d_k \neq 0$ and $d_i \in \{0,1,2,\dots,10\}$ for all $i$. For instance, the integer $N = 10$ has two base 10 over-expansions: $10 = 10 \cdot 10^0$ and the usual base 10 expansion $10 = 1 \cdot 10^1 + 0 \cdot 10^0$. Which positive integers have a unique base 10 over-expansion?

Let $A$ be an $m \times n$ matrix with rational entries. Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A$. Show that the rank of $A$ is at least 2.

Let $S$ be the set of all positive integers that are not perfect squares. For $n$ in $S$, consider choices of integers $a_1, a_2, \dots, a_r$ such that $n < a_1< a_2 < \cdots < a_r$ and $n \cdot a_1 \cdot a_2 \cdots a_r$ is a perfect square, and let $f(n)$ be the minumum of $a_r$ over all such choices. For example, $2 \cdot 3 \cdot 6$ is a perfect square, while $2 \cdot 3$, $2 \cdot 4$, $2 \cdot 5$, $2 \cdot 3 \cdot 4$, $2 \cdot 3 \cdot 5$, $2 \cdot 4 \cdot 5$, and $2 \cdot 3 \cdot 4 \cdot 5$ are not, and so $f(2) = 6$. Show that the function $f$ from $S$ to the integers is one-to-one.

For positive integers $n$, let the numbers $c(n)$ be determined by the rules $c(1) = 1$, $c(2n) = c(n)$, and $c(2n+1) = (-1)^n c(n)$. Find the value of $$\sum_{n=1}^{2013} c(n) c(n+2).$$

Let $q$ and $r$ be integers with $q > 0$, and let $A$ and $B$ be intervals on the real line. Let $T$ be the set of all $b+mq$ where $b$ and $m$ are integers with $b$ in $B$, and let $S$ be the set of all integers $a$ in $A$ such that $ra$ is in $T$. Show that if the product of the lengths of $A$ and $B$ is less than $q$, then $S$ is the intersection of $A$ with some arithmetic progression.

Let $\FF_p$ denote the field of integers modulo a prime $p$, and let $n$ be a positive integer. Let $v$ be a fixed vector in $\FF_p^n$, let $M$ be an $n \times n$ matrix with entries of $\FF_p$, and define $G: \FF_p^n \to \FF_p^n$ by $G(x) = v + Mx$. Let $G^{(k)}$ denote the $k$-fold composition of $G$ with itself, that is, $G^{(1)}(x) = G(x)$ and $G^{(k+1)}(x) = G(G^{(k)}(x))$. Determine all pairs $p, n$ for which there exist $v$ and $M$ such that the $p^n$ vectors $G^{(k)}(0)$, $k=1,2,\dots,p^n$ are distinct.

Let $p$ be an odd prime number such that $p \equiv 2 \pmod{3}$. Define a permutation $\pi$ of the residue classes modulo $p$ by $\pi(x) \equiv x^3 \pmod{p}$. Show that $\pi$ is an even permutation if and only if $p \equiv 3 \pmod{4}$.

For which positive integers $n$ is there an $n \times n$ matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

Let $h$ and $k$ be positive integers. Prove that for every $\epsilon > 0$, there are positive integers $m$ and $n$ such that $$\epsilon < |h \sqrt{m} - k \sqrt{n}| < 2\epsilon.$$

Let $S$ be the set of all ordered triples $(p,q,r)$ of prime numbers for which at least one rational number $x$ satisfies $px^2 + qx + r =0$. Which primes appear in seven or more elements of $S$?

Let $p$ be an odd prime. Show that for at least $(p+1)/2$ values of $n$ in $\{0,1,2,\dots,p-1\}$, $$\sum_{k=0}^{p-1} k! n^k \qquad \mbox{is not divisible by $p$.}$$

Given a positive integer $n$, what is the largest $k$ such that the numbers $1,2,\dots,n$ can be put into $k$ boxes so that the sum of the numbers in each box is the same? [When $n=8$, the example $\{1,2,3,6\}, \{4,8\}, \{5,7\}$ shows that the largest $k$ is at least 3.]

Prove that for each positive integer $n$, the number $10^{10^{10^n}} + 10^{10^n} + 10^n - 1$ is not prime.

Given that $A$, $B$, and $C$ are noncollinear points in the plane with integer coordinates such that the distances $AB$, $AC$, and $BC$ are integers, what is the smallest possible value of $AB$?

There are 2010 boxes labeled $B_1, B_2, \dots, B_{2010}$, and $2010n$ balls have been distributed among them, for some positive integer $n$. You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving exactly $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?

Let $S$ be a set of rational numbers such that

1. (a)
   $0 \in S$;
2. (b)
   If $x \in S$ then $x+1\in S$ and $x-1\in S$; and
3. (c)
   If $x\in S$ and $x\not\in\{0,1\}$, then $\frac{1}{x(x-1)}\in S$.

Must $S$ contain all rational numbers?

Is there a finite abelian group $G$ such that the product of the orders of all its elements is $2^{2009}$?

Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example, $$\frac{10}{9} = \frac{2!\cdot 5!}{3!\cdot 3! \cdot 3!}.$$ \,

Prove that for every positive integer $n$, there is a sequence of integers $a_0, a_1, \dots, a_{2009}$ with $a_0 = 0$ and $a_{2009} = n$ such that each term after $a_0$ is either an earlier term plus $2^k$ for some nonnegative integer $k$, or of the form $b\,\mathrm{mod}\,c$ for some earlier positive terms $b$ and $c$. [Here $b\,\mathrm{mod}\,c$ denotes the remainder when $b$ is divided by $c$, so $0 \leq (b\,\mathrm{mod}\,c) < c$.]

Start with a finite sequence $a_1, a_2, \dots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $\mathrm{gcd}(a_j, a_k)$ and $\mathrm{lcm}(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note: gcd means greatest common divisor and lcm means least common multiple.)

What is the maximum number of rational points that can lie on a circle in $\mathbb{R}^2$ whose center is not a rational point? (A rational point is a point both of whose coordinates are rational numbers.)

Let $p$ be a prime number. Let $h(x)$ be a polynomial with integer coefficients such that $h(0), h(1), \dots, h(p^2-1)$ are distinct modulo $p^2$. Show that $h(0), h(1), \dots, h(p^3-1)$ are distinct modulo $p^3$.