Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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}$?

Added:

$$\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$.

share|improve this answer
    
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}$

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.