could anyone help me with a small problem?
I need to find the least natural number $n$, $n>1$ for which the statement is true.
Statement: For any $n$ natural numbers, we can find two, $a$ and $b$, such that $ a^2-b^2 $ can be divided by 595
could anyone help me with a small problem?
I need to find the least natural number $n$, $n>1$ for which the statement is true.
Statement: For any $n$ natural numbers, we can find two, $a$ and $b$, such that $ a^2-b^2 $ can be divided by 595
This is mainly a Pigeonhole Principle problem with a bit of number theory thrown in.
Note that $595=5\times 7\times 17$. Let's consider first the problem if we replace $595$ with $5$:
In order for $a^2-b^2$ to be divisible by $5$, you need $a^2$ and $b^2$ to have the same remainders modulo $5$. There are three possible remainders a square can have when divided by $5$: $0$, $1$, and $4$. That means that if you have at least four numbers in your set, you are guaranteed that two of them will have squares whose remainders are the same.
Similarly, for $7$, you have 4 possible remainders for squares: $0$, $1$, $2$, and $4$. So you would need at least $5$ numbers to ensure the difference of the squares of two of them is divisible by $7$.
What about divisible by $35$? You need both their remainders modulo $5$ and modulo $7$ to match. There are 3 possible remainders modulo $5$, and $4$ possible remainders modulo $7$, so there are 12 possible combinations; so you need at least $13$ numbers to ensure you can get $a^2-b^2$ divisible by $35$.
With $17$, there are $9$ possible remainders for squares.
So: a number's square can have any of $3$ remainders modulo $5$, any of $4$ remainders modulo $7$, and any of $9$ remainders modulo $17$. That means that it can have any of $3\times 4\times 9 = 108$ remainders modulo $595$.
So $109$ numbers will definitely be enough: if you have $109$ natural numbers, then there must be two of them, $a$ and $b$, with $a\neq b$ such that $a^2$ and $b^2$ have the same remainders modulo $5$, $7$, and $17$ (and hence modulo $595$).
Now the question is: can you get away with fewer than $109$?
No. For each possible combination of remainders modulo $5$, $7$, and $17$, the Chinese Remainder Theorem ensures the existence of an integer $m$ that has exactly those remainders; so you can find a set with exactly $108$ natural numbers, and where the remainders when dividing their square modulo $595$ are all pairwise distinct.
HINT $\ $ The problem reduces to counting the number of squares in $\rm\:\mathbb Z_{595}\ :=\ \mathbb Z\:\ (mod\ 595)\:.\:$
By CRT (Chinese Remainder) we have a ring isomorphism $\rm\:h\!:\ \mathbb Z_{595} \cong \mathbb Z_5 \times \mathbb Z_7 \times \mathbb Z_{17} $
This isomorphism $\rm\:h\:$ restricts to a bijection on squares, namely $\rm\ \mathbb Z_{595}^2 \cong \mathbb Z_5^2 \times \mathbb Z_7^2 \times \mathbb Z_{17}^2$
since, denoting $\rm\: h(n) = (a,b,c),\: $ we have $\rm\ h(n^2) = (h(n))^2 = (a,b,c)^2 = (a^2,b^2,c^2)\:. $
So an element of $\rm\:\mathbb Z_{595}\:$ is a square iff this is true of its images in each component factor $\rm\:\mathbb Z_p\:.\:$
Thus the problem reduces to counting the squares in each component $\rm\:\mathbb Z_p\:,\:$ which is easy.
NOTE $ $ The same product decomposition works for counting the size of the image of any polynomial map $\rm\:f(x)\in \mathbb Z[x]\:$ since such polynomial maps commute with ring homomorphisms $\rm\ h(f(n)) = f(h(n)) =\: f(a,b,c) = (f(a),f(b),f(c))\:.\ $ Hence an element of $\rm\:\mathbb Z_{595}\:$ has form $\rm\:f(n)\:$ iff it has that form in each factor in the product decomposition. The decomposition reduction works precisely because ring homomorphisms preserve the form of polynomials, e.g. squares.
The condition that 595 divides $a^2-b^2$ can be translated to $a^2\equiv b^2$ mod 595. If $m$ is the number of squares in $\mathbb{Z}/595\mathbb{Z}$ then if we take m+1 natural numbers by the pigeon hole principle two of them must have the same square mod 595. We can also give a set of integers of size $m$ such that the squares fall into all the different quadratic residue classes mod 595, so m+1 will be minimal.
With the chinese remainder theorem you can calculate the number of squares. Unfortunately I have to go, if necessary I'll expand on my answer tomorrow!