Putnam Archive — Abstract Algebra

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 $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 $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 $G$ is a finite group generated by the two elements $g$ and $h$, where the order of $g$ is odd. Show that every element of $G$ can be written in the form $$g^{m_1} h^{n_1} g^{m_2} h^{n_2} \cdots g^{m_r} h^{n_r}$$ with $1 \leq r \leq |G|$ and $m_1, n_1, m_2, n_2, \ldots, m_r, n_r \in \{-1, 1\}$. (Here $|G|$ is the number of elements of $G$.)

\,

In the 75th annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible $n \times n$ matrices with entries in the field $\mathbb{Z}/p \mathbb{Z}$ of integers modulo $p$, where $n$ is a fixed positive integer and $p$ is a fixed prime number. The rules of the game are:

1. (1)
   A player cannot choose an element that has been chosen by either player on any previous turn.
2. (2)
   A player can only choose an element that commutes with all previously chosen elements.
3. (3)
   A player who cannot choose an element on his/her turn loses the game.

Patniss takes the first turn. Which player has a winning strategy? (Your answer may depend on $n$ and $p$.)

Let $*$ be a commutative and associative binary operation on a set $S$. Assume that for every $x$ and $y$ in $S$, there exists $z$ in $S$ such that $x * z = y$. (This $z$ may depend on $x$ and $y$.) Show that if $a,b,c$ are in $S$ and $a*c = b*c$, then $a=b$.

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}$.

Let $G$ be an abelian group with $n$ elements, and let $$\{g_1=e,g_2,\dots,g_k\} \subsetneqq G$$ be a (not necessarily minimal) set of distinct generators of $G$. A special die, which randomly selects one of the elements $g_1,g_2,...,g_k$ with equal probability, is rolled $m$ times and the selected elements are multiplied to produce an element $g \in G$. Prove that there exists a real number $b \in (0,1)$ such that

$$\lim_{m\to\infty} \frac{1}{b^{2m}} \sum_{x\in G} \left(\mathrm{Prob}(g=x) - \frac{1}{n}\right)^2$$ is positive and finite.

Let $G$ be a group, with operation $*$. Suppose that

1. (i)
   $G$ is a subset of $\mathbb{R}^3$ (but $*$ need not be related to addition of vectors);
2. (ii)
   For each $\mathbf{a},\mathbf{b} \in G$, either $\mathbf{a}\times \mathbf{b} = \mathbf{a}*\mathbf{b}$ or $\mathbf{a}\times \mathbf{b} = 0$ (or both), where $\times$ is the usual cross product in $\mathbb{R}^3$.

Prove that $\mathbf{a} \times \mathbf{b} = 0$ for all $\mathbf{a}, \mathbf{b} \in G$.

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

Prove that there exists a constant $c>0$ such that in every nontrivial finite group $G$ there exists a sequence of length at most $c \log |G|$ with the property that each element of $G$ equals the product of some subsequence. (The elements of $G$ in the sequence are not required to be distinct. A subsequence of a sequence is obtained by selecting some of the terms, not necessarily consecutive, without reordering them; for example, $4, 4, 2$ is a subsequence of $2, 4, 6, 4, 2$, but $2, 2, 4$ is not.)

Suppose that a finite group has exactly $n$ elements of order $p$, where $p$ is a prime. Prove that either $n=0$ or $p$ divides $n+1$.

Consider a set $S$ and a binary operation $*$, i.e., for each $a,b\in S$, $a*b\in S$. Assume $(a*b)*a=b$ for all $a,b\in S$. Prove that $a*(b*a)=b$ for all $a,b\in S$.

Let $G$ be a group with identity $e$ and $\phi:G\rightarrow G$ a function such that $$\phi(g_1)\phi(g_2)\phi(g_3)=\phi(h_1)\phi(h_2)\phi(h_3)$$ whenever $g_1g_2g_3=e=h_1h_2h_3$. Prove that there exists an element $a\in G$ such that $\psi(x)=a\phi(x)$ is a homomorphism (i.e. $\psi(xy)=\psi(x)\psi(y)$ for all $x,y\in G$).

Let $S$ be the set of ordered triples $(a, b, c)$ of distinct elements of a finite set $A$. Suppose that

1. $(a,b,c) \in S$ if and only if $(b,c,a) \in S$;
2. $(a,b,c) \in S$ if and only if $(c,b,a) \notin S$;
3. $(a,b,c)$ and $(c,d,a)$ are both in $S$ if and only if $(b,c,d)$ and $(d,a,b)$ are both in $S$.

Prove that there exists a one-to-one function $g$ from $A$ to $R$ such that $g(a) < g(b) < g(c)$ implies $(a,b,c) \in S$. Note: $R$ is the set of real numbers.

Let $S$ be a set of real numbers which is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given that the product of any {three} (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T,U$ is closed under multiplication.

Let $f_1, \dots, f_{10}$ be bijections of the set of integers such that for each integer $n$, there is some composition $f_{i_1} \circ f_{i_2} \circ \cdots \circ f_{i_m}$ of these functions (allowing repetitions) which maps 0 to $n$. Consider the set of 1024 functions $$\mathcal{F} = \{f_1^{e_1} \circ f_2^{e_2} \circ \cdots \circ f_{10}^{e_{10}}\},$$ $e_i = 0$ or 1 for $1 \leq i \leq 10$. ($f_i^0$ is the identity function and $f_i^1 = f_i$.) Show that if $A$ is any nonempty finite set of integers, then at most 512 of the functions in $\mathcal{F}$ map $A$ to itself.

Let $\MM$ be a set of real $n \times n$ matrices such that

• (i)
  $I \in \MM$, where $I$ is the $n \times n$ identity matrix;
• (ii)
  if $A \in \MM$ and $B \in \MM$, then either $AB \in \MM$ or $-AB \in \MM$, but not both;
• (iii)
  if $A \in \MM$ and $B \in \MM$, then either $AB = BA$ or $AB = -BA$;
• (iv)
  if $A \in \MM$ and $A \neq I$, there is at least one $B \in \MM$ such that $AB = - BA$.

Prove that $\MM$ contains at most $n^2$ matrices.

Let $G$ be a finite group of order $n$ generated by $a$ and $b$. Prove or disprove: there is a sequence $$g_1, g_2, g_3, \dots, g_{2n}$$ such that

• (1)
  every element of $G$ occurs exactly twice, and
• (2)
  $g_{i+1}$ equals $g_i a$ or $g_i b$ for $i = 1, 2, \dots, 2n$. (Interpret $g_{2n+1}$ as $g_1$.)

Let $\alpha=1+a_1x+a_2x^2+\cdots$ be a formal power series with coefficients in the field of two elements. Let $$a_n = \begin{cases} 1 & \text{if every block of zeros in the binary expansion of $n$ has an even number of zeros in the block} \\[.3in] 0 & \text{otherwise.} \end{cases}$$ (For example, $a_{36}=1$ because $36=100100_2$ and $a_{20}=0$ because $20=10100_2.$) Prove that $\alpha^3+x\alpha+1=0.$

Let $S$ be a non-empty set with an associative operation that is left and right cancellative ($xy=xz$ implies $y=z$, and $yx=zx$ implies $y=z$). Assume that for every $a$ in $S$ the set $\{a^n:\,n=1, 2, 3, \ldots\}$ is finite. Must $S$ be a group?

Let $F$ be a field in which $1+1 \neq 0$. Show that the set of solutions to the equation $x^2+y^2=1$ with $x$ and $y$ in $F$ is given by $(x,y)=(1,0)$ and $$(x,y) = \left( \frac{r^2-1}{r^2+1}, \frac{2r}{r^2+1} \right)$$ where $r$ runs through the elements of $F$ such that $r^2\neq -1$.

Let $F$ be the field of $p^2$ elements, where $p$ is an odd prime. Suppose $S$ is a set of $(p^2-1)/2$ distinct nonzero elements of $F$ with the property that for each $a\neq 0$ in $F$, exactly one of $a$ and $-a$ is in $S$. Let $N$ be the number of elements in the intersection $S \cap \{2a: a \in S\}$. Prove that $N$ is even.

Let $\Gamma$ consist of all polynomials in $x$ with integer coefficients. For $f$ and $g$ in $\Gamma$ and $m$ a positive integer, let $f \equiv g \pmod{m}$ mean that every coefficient of $f-g$ is an integral multiple of $m$. Let $n$ and $p$ be positive integers with $p$ prime. Given that $f,g,h,r$ and $s$ are in $\Gamma$ with $rf+sg\equiv 1 \pmod{p}$ and $fg \equiv h \pmod{p}$, prove that there exist $F$ and $G$ in $\Gamma$ with $F \equiv f \pmod{p}$, $G \equiv g \pmod{p}$, and $FG \equiv h \pmod{p^n}$.

Let $G$ be a finite set of real $n\times n$ matrices $\{M_i\}$, $1 \leq i \leq r$, which form a group under matrix multiplication. Suppose that $\sum_{i=1}^r \mathrm{tr}(M_i)=0$, where $\mathrm{tr}(A)$ denotes the trace of the matrix $A$. Prove that $\sum_{i=1}^r M_i$ is the $n \times n$ zero matrix.