Given a prime number $p > 2$. Find the least $n\in Z_+$, for which every set of $n$ perfect squares not divisible by $p$ contains nonempty subset with product of all it's elements equal to $1\ (\text{mod}\ p)$
Problem
Source:
Tags: number theory, prime numbers
03.12.2018 22:04
For the ones, who want the version "prove that n=..."
I can't wait to see your elementary proofs.
03.12.2018 22:25
Lemma If $ m$ is a positive integer and $ a_{1} ,...,a_{m}$ is an integer sequence, then there exists a nonempty subset $ S$ of $ [ 1,m] \cap \mathbb{N}$ such that $ \sum _{j\in S} a_{j} \equiv 0\pmod m$. (It's well known and easy. Prove it yourself if you need) Solution For each perfect square $ q_{i}$ not divisible by $ p$, we can take an integer $ e_{i}( 0\leq e_{i} < (p-1)/2)$ such that $ q_{i} \equiv g^{2e_{i}}\pmod p$ where $ g$ is a primitive root modulo $ p$. So we have $ \prod^{n}_{i=1} q_{i} \equiv 1\pmod p\ \ \Leftrightarrow \ \sum ^{n}_{i=1} 2e_{i} \equiv 0\pmod{p-1}\ \ \ \Leftrightarrow \ \ \sum ^{n}_{i=1} e_{i} \equiv 0\pmod{(p-1)/2}$ Thus, the least $ n$ which satisfies the condition is not greater than $(p-1) /2$. In fact, this is the exactly what we wanted. (Just consider the case $ e_{1} =e_{2} =...=e_{n} =1$)
05.12.2018 18:56
For $p=3$ conclusion is obvious, we take one-element subset. Let further $p>3$. If we can choose required subset for any $n$ perfect squares, then we can do it for any $n+1$ perfect squares. Equivalently, if for certain $n$ perfect squares we can't choose required subset, then it's imposible for some $n-1$ perfect squares. So it's sufficient to show that, for certain set of $\frac{p-1}{2} -1$ perfect squares choice is impossible, but choice exists for any set of $\frac{p-1}{2}$ perfect squares. Proof of first sentence: take $\frac{p-1}{2} -1$ numbers: $2^2$. SInce $p|2^{p-1}-1$,we can't have $p|2^{p-3}-1$, because it leads to $p|3$. Hence $2^{2\cdot \left(\frac{p-1}{2} -1\right)}$ isn't divisible by $p$. Second sentence proof: consider set $\lbrace x_1^2,x_2^2,...,x_n^2\rbrace$, where $x_i\in Z$ and $n=\frac{p-1}{2}$. Assume contrary, that choice of required subset is impossible. Numbers $x_1^2,(x_1x_2)^2,...,(x_1x_2\cdot...\cdot x_n)^2$ don't give residue $0$ nor $1$ (respectively from assumption in the task and contrary assumption) when divided by $p$. For $p>2$ we have $\frac{p-1}{2}-1$ quadratic residues modulo $p$ different than $0$ and $1$. By pigeonhole principle there exist $k,l\in Z\wedge 1\le k<l\le n$ for which $p|(x_1...x_k)^2-(x_1...x_l)^2=(x_1...x_l)^2((x_{l+1}...x_k)^2-1)$. Numbers $x_i$ aren't divisible by $p$, so $p|(x_{l+1}...x_k)^2-1$. That's a contradiction with contrary assumption.
13.04.2020 00:45
solved also here in the MOP 2006 wording (Blue Group NT 4) Quote: Let $p$ be an odd prime, and let $S = \{n_{1},n_{2}, \cdots, n_{k}\}$ be an arbirtrary set of perfect squares relatively prime to $p$. Compute the smallest $k$ such that there necessarily exists a subset of $S$ with the product of its elements one more than a multiple of $p$. PS. this solution might be the same with above, but the reason for this comment is to invest in getting all ideas in one post for the 2006 MOP Homework post collection