Find the greatest positive integer $N$ with the following property: there exist integers $x_1, . . . , x_N$ such that $x^2_i - x_ix_j$ is not divisible by $1111$ for any $i\ne j.$
Problem
Source:
Tags: number theory
bobthesmartypants
01.05.2016 23:07
We see that $x_i^2-x_ix_j=x_i(x_i-x_j)\not\equiv 0\pmod{1111}$, so $1111\nmid x_i$ and no two $i\ne j$ have $x_i\equiv x_j\pmod{1111}$. This means the maximum value of $N$ possible is $N=1110$, where $x_1, x_2, \ldots , x_{1110}$ are precisely the non-zero residues mod $1111$. EDIT: whoops obviously $1111$ is not prime so do my argument on its prime factors and use CRT to get $(11-1)\cdot (101-1)=\boxed{1000}$
gandhi
01.05.2016 23:19
The answer is 1000
MathStudent2002
01.05.2016 23:20
@bob 1111 = 11 * 101, so $x_i = 11, x_j=112$ gives $x_i(x_i-x_j) = 11(-101) = 0\pmod{1111}$
shinichiman
02.05.2016 01:29
We can't have $x_i \equiv x_j \pmod{1111}$ so $N \le 1111$.
We also can't have $101 \mid x_i, x_i \equiv x_j \pmod{11}$ or $11 \mid x_i, x_i \equiv x_j \pmod{101}$. Hence, we will have a better maximum if we exclude all numbers that is divisible by $11$ (in this case $N \le 1111-101=1010$) rather than to get $N$ numbers such that $x_i \not\equiv x_j \pmod{101}$ (this case $N \le 101$). Similarly, we also have to exclude numbers that is multiple of $101$ so $N \le 1010-10=1000$.
Thus, $N \le 1000$.