# If an integer $n$ is coprime to $6$, then prove that $n^2$ leaves remainder 1 on division by 24 [duplicate]

If an integer $n$ is coprime to $6$, then prove that $n^2$ leaves remainder 1 on division by 24

I know that $n$ can be written as $6k+1$ and $6k+5$, but how to proceed?

• i would square $$6k+1$$ and $$6k+5$$ – Dr. Sonnhard Graubner Mar 22 '17 at 17:31
• You are more than halfway there with that observation. Now... for each of the two cases compute $n^2$ and group as much as you can into terms which are divisible by $24$ and terms which are not. $(6k+1)^2=36k^2+12k+1=24k^2+12(k^2+k)+1$. Is $24k^2$ divisible by $24$? Is $12(k^2+k)$ divisible by $24$? (Is $k^2+k$ divisible by $2$?) Do so similarly for $6k+5$. – JMoravitz Mar 22 '17 at 17:31

$\implies n$ is of the form $6m\pm1$ where $m$ is any integer
Now $(6m\pm1)^2=24m^2+24\cdot\dfrac{m(m\pm1)}2+1$
as $m(m\pm1)$ are even being products of two consecutive integers.
Let $\gcd(n,6) = 1$. We want $n^{2} = 24q + 1$ for some integer $q$. Note that it is equivalent to $n^{2}-1 = (n-1)(n+1) = 24q$. If $n = 6k+1$ for some integer $k$, then $(n-1)(n+1) = 36k^{2} + 12k = 24q$, that is $k(3k+1) = 2q$. Note that $k, 3k+1$ cannot be both odd. Then we find $q = k(3k+1)/2$.
Likewise, if $n = 6k+5$ for some integer $k$, then we are led to consider $(k+1)(3k+2) = 2q$. Again $k+1, 3k+2$ cannot be both odd, so taking $q := (k+1)(3k+2)/2$ suffices.