I am interested in seeing examples of research problems which fall into one of the two following categories:

A problem which is solved in the case of primes (or prime powers), but which remains open in the case of composite integers.

A problem which historically was first solved for primes, and then significant additional work was needed to prove the result for all integers.

This is a rather broad question, so I'm mainly interested in combinatorial or algebraic problems that appear to be easy over primes because of the existence of certain structures which exist for primes, but not for all integers (e.g., for any prime power $q$, there is a finite field $\mathbb{F}_q$ of size $q$, but there is no finite field of size $6$).

An example of the sort of problem I'm looking for in the first category is *tesselations of integers*. We say a finite set $A$ of integers is a "tile" if there exists an infinite set of integers $X$ such that for every integer $n$, the equation $n = a +x$ has exactly one solution $(a,x)\in A\times X$. In the 70s, Newman showed that for any prime power $q$, there is a simple characterization for the set of tiles $A$ of size $q$. Additional work has characterized the possible tile sets $A$ when $|A|$ has very few distinct prime factors, for example, but in general characterizing the possible tile sets of size $n$ for an arbitrary integer $n$ remains open.

7more comments