# a problem on set of the squares of $1200$ consecutive natural numbers

Let $N$ be the set of the squares of $1200$ consecutive natural numbers. How many elements of $N$ leave a remainder of $1$ when divided by $24$?

I am totally stuck.

-

HINT: Divide the $1200$ consecutive numbers into $50$ blocks of $24$ consecutive numbers. Each block will contain one number from each congruence class modulo $24$. What are $0^2,1^2,2^2,\dots,23^2$ modulo $24$? How many of these squares are $1\pmod{24}$?

$$\begin{array}{c|c|c|c} r&r^2&r^2\bmod{24}\\ \hline 0&0&0\\ 1&1&\underline{1}\\ 2&4&4\\ 3&9&9\\ 4&16&16\\ 5&25&\underline{1}\\ 6&36&12\\ 7&49&\underline{1}\\ 8&64&16\\ 9&81&9\\ 10&100&4\\ 11&121&\underline{1}\\ 12&144&0 \end{array}$$

The numbers $13,14,\dots,23$ are congruent to $-11,-10,\dots,-1$ modulo $24$, so they have the same squares in reverse order. Thus, the values of $r\in\{0,1,2,\dots,23\}$ for which $r^2\equiv1\pmod{24}$ are $1,5,7,11$ and their negatives modulo $24$, i.e., $23,19,17$, and $13$.

In other words, the members of $8$ of the $24$ residue classes modulo $24$ have squares congruent to $1$ modulo $24$ and therefore leave a remainder of $1$ when divided by $24$. (There are other ways to arrive at this figure: these are precisely the $r\in\{0,1,2,\dots,23\}$ that have multiplicative inverses modulo $24$, and depending on what you’ve already studied, you may know that these are the numbers in $\{0,1,2,\dots,23\}$ that are relatively prime to $24$.)

Any string of $1200$ consecutive integers contains $50$ members of each congruence class modulo $24$.

-
did not understand.will you explain please.thanks for your time – pinti Jan 23 '13 at 2:11
@pinti: First let’s see where we are. Do you know what I mean by a congruence class modulo $24$? – Brian M. Scott Jan 23 '13 at 2:13
yes.I know........ – pinti Jan 23 '13 at 2:16
@pinti: Okay. There’s one congruence class for each of the integers $0,1,2,\dots,23$. Suppose that $r$ is one of these $24$ numbers. If $n\equiv r\pmod{24}$, then $n^2\equiv r^2\pmod{24}$, so $n^2$ leaves a remainder of $1$ when divided by $24$ if and only if $r^2\equiv 1\pmod{24}$. For which values of $r$ is it true that $r^2\equiv 1\pmod{24}$? – Brian M. Scott Jan 23 '13 at 2:20
@Ross: Thanks. The $0$ for the congruence class of $3^2$ was probably a genuine typo, but I’ve no idea how I think managed to count it as a $1$. – Brian M. Scott Apr 23 '13 at 13:24

Let's consider, $$a^2\equiv1\pmod{24}$$

Using Carmichael Function, $$\lambda(24)=\text{ lcm }(\lambda(8),\lambda(3))=\text{ lcm }(2,2)=2$$

So, $$a^2\equiv1\pmod{24}$$ for all $a$ relatively prime to $24$

Now the number of numbers $<24$ and co-prime with $24$ is $\phi(24)=\phi(3)\phi(8)=2\cdot4=8$

So, in any set of $24$ consecutive numbers (as they form a Complete Residue System), we shall find exactly $8$ values of $a$ such that $a^2\equiv1\pmod{24}$

-

every natural number can be expressed by $12m+n (0 \leq n \leq 11)$, the square shall be $(12m+n)^{2}=144m^{2}+24mn+n^{2}$, thus $(12m+n)^{2} \mod 24=n^{2} \mod 24(0 \leq n \leq 11)$, you can get that when $n=1,5,7,11, (12m+n)^{2} \mod 24 =1$.

-