$N^2$ leaves a remainder of $1$ when divided by $24$. What are the possible remainders we can get if we divide $N$ by $12$?
By John Thompson
My solution approach is as below :-
$Rem[\frac{N^2}{24}] = 1$
$\Rightarrow Rem[\frac{N \times N}{24}] = 1$
$\Rightarrow Rem[\frac{N}{24}] \times Rem[\frac{N}{24}] = 1$
$\Rightarrow \text{This can only happen when both are 1 i.e. } Rem[\frac{N}{24}]=1$
So we can say that $N=24k+1$ and when we divide this $N$ by $12$ we should always get a remainder of $1$ but the answer provided for this problem is different and looks like I am wrong. Please help me on this !
Thanks in advance !
$\endgroup$2 Answers
$\begingroup$Let's suppose the remainder of $N$ when divided by $12$ is some integer $r \in \{0, 1, 2, \ldots, 11\}$. That is to say, $$N = 12q + r,$$ where $q$ is the quotient. Then $$N^2 = (12q + r)^2 = 144q^2 + 24qr + r^2,$$ and we are told that this has a remainder of $1$ when divided by $24$. Since $144 = 6(24)$, the first two terms on the right hand side are always divisible by $24$ and leave a remainder of $0$. So $r^2$, when divided by $24$, must leave a remainder of $1$.
Among the choices $r \in \{0, 1, 2, \ldots, 11\}$, clearly if $r$ is even, $r^2$ is also even, and cannot leave an odd remainder. This reduces our search to $r \in \{1, 3, 5, 7, 9, 11\}$, for which the squares are $$r^2 \in \{1, 9, 25, 49, 81, 121\}.$$ Then we see$$\begin{align} 1 &= 24(0) + 1, \\ 9 &= 24(0) + 9, \\ 25 &= 24(1) + 1, \\ 49 &= 24(2) + 1, \\ 81 &= 24(3) + 9, \\ 121 &= 24(5) + 1, \end{align}$$so the permissible remainders for $N$ upon division by $12$ are $$r \in \{1, 5, 7, 11\}.$$
$\endgroup$ $\begingroup$We need to check every possible square modulo $24$. However, this is made easier because $24$ has many factors, and any number not coprime to it can never give $1$ when squared.$$N^2\equiv1\bmod24\implies N=\pm1,\pm5,\pm7,\pm11\bmod24\implies N\equiv1,5,7,11\bmod12$$
$\endgroup$ 1
