1
$\begingroup$

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

  • 1
    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$?2012-01-13

3 Answers 3

9

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.

  • 0
    @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.2012-01-13
4

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.

1

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!

  • 0
    Note that all answers suggest the same solution to the problem though.2012-01-14