Let $p$ be a prime number and let $A$ be a set of positive integers that satisfies the following conditions:
(i) the set of prime divisors of the elements in $A$ consists of $p-1$ elements;
(ii) for any nonempty subset of $A$, the product of its elements is not a perfect $p$-th power.
What is the largest possible number of elements in $A$ ?
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
Let our primes be $q_1, q_2, \ldots, q_{p-1}$. By considering the exponents of each prime, our problem reduces to finding the largest number of (not necessarily distinct) $p-1$-tuples of elements in $\mathbb{Z}/p\mathbb{Z}$ such that the sum of any set of elements in the set of them is not $(0,0,\ldots,0)$ mod $p$.
We have that $k=(p-1)^2$. $(p-1)^2$ is attainable, as the set $\{ \underbrace{(1, 0, 0, \ldots, 0)}_{p-1 \mbox{ times }}, \underbrace{(0,1, 0, \ldots, 0)}_{p-1 \mbox{ times }}, \ldots, \underbrace{(0, 0, 0, \ldots, 1)}_{p-1 \mbox{ times }} \}$ works.
We will now show that with $(p-1)^2 + 1$ tuples, we can find a non-empty set of them that sum to 0. Let the elements of our set be $T_1 = (e_{1,1}, e_{2,1}, \ldots, e_{p-1,1}), T_2 = (e_{1,2}, e_{2,2}, \ldots, e_{p-1,2}), \ldots, T_{(p-1)^2 + 1} = (e_{1,(p-1)^2 + 1}, e_{2, (p-1)^2 + 1}, \ldots, e_{p-1,(p-1)^2 + 1})$.
Consider the following system of equations in the $(p-1)^2 + 1$ variables $a_1, a_2, \ldots, a_{(p-1)^2 + 1}$:
\begin{align*}
a_1^{p-1} e_{1,1} + a_2^{p-1} e_{2, 1} + \cdots + a_{p-1}^{p-1} e_{p-1,1} &\equiv 0 \pmod{p} \\
a_1^{p-1} e_{1,2} + a_2^{p-1} e_{2, 2} + \cdots + a_{p-1}^{p-1} e_{p-1,2} &\equiv 0 \pmod{p} \\
& \vdots \\
a_1^{p-1} e_{1,(p-1)^2 + 1} + a_2^{p-1} e_{2, (p-1)^2 + 1} + \cdots + a_{p-1}^{p-1} e_{p-1,(p-1)^2 + 1} &\equiv 0 \pmod{p}.
\end{align*}.
The sum of the degrees of this equation is $(p-1)^2 < (p-1)^2 + 1$. This system has the solution $(a_1, a_2, \ldots, a_{p-1}) = (0, 0, \cdots, 0)$, so we may apply Chevalley's theorem to find a solution $(a_1, a_2, \ldots, a_{p-1})$ in which not each entry of the tuple is 0 modulo $p$.
Let $a_{b_1}, a_{b_2}, \ldots, a_{b_n}$ be the nonzero entries. Note that $a_i^{p-1} \equiv 0 \pmod{p}$ iff $i \neq b_j$ for any $j$, and it is 1 iff $i = b_j$ for some $j$. Therefore, we have that
\begin{align*}
e_{b_1, 1} + e_{b_2, 1} + \cdots + e_{b_n,1} &\equiv 0 \pmod{p} \\
e_{b_1, 2} + e_{b_2, 2} + \cdots + e_{b_n, 1} &\equiv 0 \pmod{p} \\
& \vdots \\
e_{b_1, (p-1)^2 + 1} + e_{b_2, (p-1)^2 + 1} + \cdots + e_{b_n, (p-1)^2 + 1} &\equiv 0 \pmod{p}
\end{align*}
It follows that the sum of the $T_{b_1}, T_{b_2}, \ldots, T_{b_n}$ is $(0,0,\ldots,0)$ mod $p$, so our proof is complete.
Solution from Twitch Solves ISL:
Let $D = p-1$. Then the question (thinking in terms of the exponents) can be phrased as follows:
What's the largest multiset of vectors in ${\mathbb F}_p^{D}$ such that no nonempty subset has zero sum?
We claim the answer is $D \cdot (p-1)$. A construction is given by taking
$p-1$ copies of the vector $\left< 1, 0, \dots, 0\right>$;
$p-1$ copies of the vector $\left< 0, 1, \dots, 0\right>$;
\dots;
$p-1$ copies of the vector $\left< 0, 0, \dots, 1 \right>$.
To show it's best possible, suppose we have vectors $v_1$, \dots, $v_N$ with coordinates given as \[ v_k = \left< v_{k,1}, v_{k,2}, \dots, v_{k,D} \right> \qquad k = 1, 2, \dots, N. \]Then, we construct the polynomial \[ F(X_1, \dots, X_N) = \prod_{i=1}^D \left[ 1 - \left( \sum_{k=1}^N X_k v_{k,j} \right)^{p-1} \right] - \prod_{i=1}^N (1-X_i) \]If we imagine the $X_i \in \{0,1\}$ as Bernoulli random variables indicating whether $v_k$ is used in a set or not, then $F(X_1, \dots, X_N) \neq 0$ exactly when the $X_i$'s equal to $1$ correspond to a nonempty subset of the vectors which have vanishing sum.
Now assume for contradiction $N < D \cdot (p-1)$. Then the largest degree term is given in the latter product; it is exactly $(-1)^{N+1} X_1 X_2 \dots X_N$. So if we quote Alon's combinatorial nullstellensatz, it now follows that there is a choice of $X_i \in \{0,1\}$ such that $F(X_1, \dots, X_N) \neq 0$ which is a contradiction.
Solution with derfu37 and a hint to use Chevalley's from Al3jandro0000.
We claim the answer is $(p-1)^2$. This is achievable by taking the set
\[ A = \{ q_i^{pj+1}\vert(i,j)\in\{1,\ldots,p-1\}^2 \} \]where $\{q_i\}_{i=1}^{\infty}$ is the sequence of primes. Now we show $|A|>(p-1)^2$ is impossible. Let $n=|A|$. Note that by condition (i) we can represent the elements of $A$ as vectors in $\mathbb F_p^{p-1}$. Let these be
\[ v_i = (e_{i1},\ldots,e_{i(p-1)})\text{ for } 1\le i\le n. \]Now, we define $f_j\colon\mathbb F_p^n\rightarrow\mathbb F_p^n$ as
\[ f_j(x_1,\ldots,x_n) = \sum_{i=1}^n x_i^{p-1}e_{ji}. \]Consider the system of equations $f_j(x_1,\ldots,x_n)=0$ for $1\le j\le p-1$. Note that $(0,\ldots,0)$ is a trivial solution. Suppose for the sake of contradiction that $n>(p-1)^2$. Then, we have
\[ n>(p-1)^2=(p-1)\cdot(p-1)=\sum_{j=1}^{p-1}\deg(f_j). \]Thus, quoting Chevalley's Theorem there must exist a nontrivial solution to the system. However, since $x_i^{p-1}\in{0,1}$, this nontrivial solution specifies a nonempty subset of $A$ for which the product is a perfect $p-$th power, yielding the desired contradiction. $\blacksquare$
One can easily rephrase this problem using the prime factorizations of the elements of $A$; this asks for the size of the largest multiset of vectors of $\mathbb{F}_p^{p-1}$ where no nonempty subset has a sum of zero.
The answer is $(p-1)^2$; this can be obtained by taking\[\bigcup_{\textbf{x}\in \mathbb{F}_p^{p-1} \\ |\textbf{x}|=1}\{\textbf{x} \ \text{repeated} \ p-1 \ \text{times}\}.\]Assume for contradiction that there is a solution of vectors $v_1, \ldots, v_N$ with $N>p-1$ that works, where we write\[ v_i = (e_{i1},\ldots,e_{i(p-1)}) \]for each $i$. Now define\[ f_k(x_1,\ldots,x_N) = \sum_{i=1}^N x_i^{p-1}e_{ki} \]for all $1 \le k \le p-1$. Since $(0, \ldots, 0)$ is a common root of all $f_k$, the Chevalley-Warning theorem guarantees a nontrivial root common to all $f_k$. By Fermat's Little Theorem, each $x_i^{p-1}$ is either $0$ or $1$, so there is a nonempty subset of $\{v_1, \ldots, v_N\}$ with a zero sum by using this nontrivial root, a contradiction. Hence $(p-1)^2$ is the size of the largest multiset of vectors of $\mathbb{F}_p^{p-1}$ where no nonempty subset has a sum of zero, and we are done.
Chevalley-Warning essentially nukes this.
The answer is $(p-1)^2$. For construction, pick primes $q_1, q_2, \cdots, q_{p-1}$, and use $q_1, q_1^{p+1}, \cdots, q_1^{1+p(p-2)}$ and similarly for the other $q_i$'s. This obviously satisfies both conditions.
For the proof of maximality, set the $q_i$ to be the same and choose $k = (p-1)^2 + 1$ distinct elements from $A$, which we will label $x_1$ through $ x_k$. For each $j$, let $e_{ij}$ be the exponent of $q_i$ in $x_j$.
Now, for the polynomials $$f_i(X_1, \cdots, X_k) = X_1^{p-1}e_{i1} + X_2^{p-1}e_{i2} + \cdots + X_k^{p-1} e_{ik},$$by Chevalley-Warning there exists a nontrivial solution to the system $$f_1(x_1, x_2, \cdots, x_k) \equiv f_2(x_1, x_2, \cdots, x_k) \equiv \cdots \equiv 0 \pmod p.$$Pick a subset $B$ of all nonzero $x_i$ in this set that satisfy the condition. Then by definition and Fermat's Little Theorem it follows that $\sum_{j \in B} e_{ij} \equiv 0 \pmod p$ for each $i$, thus the product of the elements in $B$ is a perfect $p$th power, contradiction.
Claim: If $x_j = (x_{j,1},\cdots, x_{j,n}) \in (\mathbb{Z}/p\mathbb{Z})^n$ ($j\in \{1,\cdots,K\}$) such that for all $e_1, \cdots, e_K \in \{0,1\}$ (not all zero), then $\sum e_jx_j \ne 0$. Then $K\le n(p-1)$ (this bound is optimal because I can have $p-1$ copies of $(\underbrace{0, \cdots, 0}_{j}, 1, \underbrace{0, \cdots, 0}_{n-1-j})$ for $j=0,\cdots,n-1$)
Proof: Assume $K\ge n(p-1)+1$. Consider the polynomial
$$P(f_1, \cdots, f_K) = \prod\limits_{j=1}^n (1-(\sum_{k=1}^K f_kx_{k,j})^{p-1})$$
If $\sum e_jx_j \ne 0 \iff$ there exists $t$ such that $\sum_k e_k x_{k,t} \ne 0$. Then $1-(\sum_k e_k x_{k,t})^{p-1}=0$ in $\mathbb{Z}/p\mathbb{Z}$. Hence $P(f_1,\cdots,f_K)=0$ for all $f_1,\cdots,f_k \in \{0,1\}$ that are not all zero, and $P(0,\cdots,0)=1$.
We first flatten the polynomial i.e. replace $f_k^j$ with $f_k$ when $j\ge 2$ (i.e. we take this polynomial and take its remainder mod $f_1^2-f_1, f_2^2-f_2, \cdots, f_K^2-f_K$). Call this polynomial $\tilde P$. Now note $$\tilde P + (1-f_1)(1-f_2)\cdots (1-f_K)$$vanishes in $\{0,1\}^K$, but one can show that $$v\colon [K] \to (\mathbb{Z}/p\mathbb{Z})^{2^K}, v_S = ( \prod\limits_{j\in S} f_j )_{(f_1,\cdots,f_k)\in \{0,1\}^K}$$are linearly independent in $\{0,1\}^K$ (or we induct by seeing this as a linear poly in $f_1$ namely $R(f_2,\cdots,f_K) f_1 + Q(f_2,\cdots,f_K)$ and since this poly is 0 when $f_1\in \{0,1\}$, $R(f_2,\cdots,f_K), Q(f_2,\cdots,f_K)$ satisfy the problem conditions for $K-1$) so $$\tilde P + (1-f_1)(1-f_2)\cdots (1-f_K) \equiv 0$$
This is absurd since $\deg \tilde P < K$
Yet another C-W nuke solution
Claim: $|A| = (p-1)^2$ is achieveable.
Proof. Let $p_n$ denote the $n$th prime for $1 \le n \le p - 1$. Then $p-1$ occurences of each $p_n$ suffices. $\blacksquare$
Claim: $(p-1)^2$ is maximal.
Proof. FTSOC assume there exists some $A$ of size $n = p^2 - 2p$. Enumerate $A$ as $a_{1}, a_{2}, \dots, a_n$ and the prime divisors as $p_1, p_2, \dots, p_n$. For each $i$, let $a_i = p_1^{c_{i1}}p_2^{c_{i2}}\dots p_n^{c_{in}}$.
Construct the $p-1$ polynomials $f_1, f_2, \dots f_{p-1}$ in ${\mathbb F}_p$ such that \[ f_i(x_1, x_2, \dots, x_n) = \sum_{j=1}^{n} c_{ij}x_j^{p-1}. \]Note that $\deg f_i = p-1$ and that $f_i$ is $0$ iff the elements of $A$ at its nonzero inputs have a product with $\nu_{p_i}$ divisible by $p$.
Since $n > \deg f_i \cdot (p-1) = (p-1)^2$, and $(0, 0, \dots, 0)$ is one of the common roots of every polynomial, by Chevalley-Warnining there exists another root, contradiction. $\blacksquare$
Let $D = p-1$. Then the question (thinking in terms of the exponents) can be phrased as follows:
What's the largest multiset of vectors in ${\mathbb F}_p^{D}$ such that no nonempty subset has zero sum?
We claim the answer is $D \cdot (p-1)$. A construction is given by taking
$p-1$ copies of the vector $\left< 1, 0, \dots, 0\right>$;
$p-1$ copies of the vector $\left< 0, 1, \dots, 0\right>$;
$......$;
$p-1$ copies of the vector $\left< 0, 0, \dots, 1 \right>$.
To show it's best possible, suppose we have vectors $v_1$, \dots, $v_N$ with coordinates given as \[ v_k = \left< v_{k,1}, v_{k,2}, \dots, v_{k,D} \right> \qquad k = 1, 2, \dots, N. \]Then, we construct the polynomial \[ F(X_1, \dots, X_N) = \prod_{i=1}^D \left[ 1 - \left( \sum_{k=1}^N X_k v_{k,j} \right)^{p-1} \right] - \prod_{i=1}^N (1-X_i) \]If we imagine the $X_i \in \{0,1\}$ as Bernoulli random variables indicating whether $v_k$ is used in a set or not, then $F(X_1, \dots, X_N) \neq 0$ exactly when the $X_i$'s equal to $1$ correspond to a nonempty subset of the vectors which have vanishing sum.
Now assume for contradiction $N < D \cdot (p-1)$. Then the largest degree term is given in the latter product; it is exactly $(-1)^{N+1} X_1 X_2 \dots X_N$. So if we quote Alon's combinatorial nullstellensatz, it now follows that there is a choice of $X_i \in \{0,1\}$ such that $F(X_1, \dots, X_N) \neq 0$ which is a contradiction. $\square$
The answer is $(p-1)^2$
Interpret each number as a $\mathbb{F}_p^{p-1}$ vector with entries corresponding to their $\nu_q$ modulo $p$: we are asked to find the largest multiset of vectors such that no nonempty subset of them sum to the $0$ vector. For a construction, we may take $p-1$ copies of each of the $p-1$ vectors with one entry equal to $1$ and the rest $0$.
I will now prove that $k:=|A|>(p-1)^2$ is impossible. To that end, suppose we had $k$ vectors $v_1,\ldots,v_k$ and the $j$-th element of $v_i$ was $a_{ij}$. Consider the following polynomial in $\mathbb{F}_p[x_1,\ldots,x_k]$:
$$P(x):=\prod_{i=1}^{k} (1-x_i)-\prod_{j=1}^{p-1} \left(1-\left(\sum_{i=1}^k a_{ij}x_i\right)^{p-1}\right).$$If we restrict $x_i \in \{0,1\}$ for all $i$, then choosing some subset of the vectors and summing them is equivalent to setting some subset of the $x_i$ to $1$ (and the rest $0$). If we choose the empty set, i.e. $x_i=0$ always, then the first and second products are both $1$. Otherwise, the first product clearly vanishes, and by hypothesis, since some entry of their sum is nonzero, Fermat's little theorem guarantees that the second product vanishes as well. Thus $P$ vanishes for any choice of $(x_1,\ldots,x_k) \in \{0,1\}^k$, but since $k>(p-1)^2$ it contains the maximal-degree term $(-1)^kx_1\ldots x_k$, which yields a contradiction by combinatorial nullstellensatz. $\blacksquare$