# Find the least natural number, for which the statement is true

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

-
Do you have any ideas? Can you see that you need to know the number of squares modulo 595 (that is, the number of squares in $\mathbb{Z}/595\mathbb{Z}$)? What would the answer to this question be if instead of 595 you had an odd prime number $p$? – Jonas Kibelbek Jan 13 '12 at 17:01

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.

-
Wow, so simple, firstly I thought I'd never understand a solution. Thanks a lot! – user1131662 Jan 13 '12 at 17:10
@user1131662 Since many students often have difficulty eliciting the essential points in arguments of this type, and since such points are not made explicit above, I have added an answer which explicitly addresses such. – Bill Dubuque Jan 13 '12 at 20:21

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!

-
I'm sorry, but I'm too stupid to understand that one. But as I hope, the solution by "Arturo Magidin" is the right one because it's wway simplier. – user1131662 Jan 13 '12 at 17:16
@user1131662: Well, I explained why it suffices to count the number of squares mod 595 and mentioned that you can do it with the chinese remainder theorem. Arturo explicitly told you how to do it and Bill's answer explains why this counting process works. Maybe my answer would have been better suited as a comment (I wanted to be more detailed and unexpectedly had to go) – Michalis Jan 14 '12 at 12:32
Note that all answers suggest the same solution to the problem though. – Michalis Jan 14 '12 at 12:33