Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$. Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.
My workings so far: I proceeded by induction. Obviously $1^2 \equiv 1 \mod 8$. Then assume that for a certain uneven number $k$ we have $k^2 \equiv 1 \mod 8$. Then the the next uneven number is $k+2$ and $(k+2)^2 = k^2 + 4k + 4 \equiv 4k + 5 \mod 8$. by the induction hypothesis. Now since $k$ is uneven we can write it as $k=2j+1$ and thus $4k+5 =8j+9 \equiv 1 \mod 8$ and we have shown what was asked for by induction.
However, in the case of a prime number $n$ I am not so certain how to proceed because I can't use induction. It comes down to proving that $24|(p^2-1)$. This is certainly the case for the first uneven prime $p \neq 3$, namely $p=5$ such that $p^2-1 =24$. How would I proceed from here, or how should I approach the problem differently? Many thanks in advance!
 A: If $n$ is odd, $n = 2 k + 1$ and $n^2 = 4 k^2 + 4 k + 1 = 4 k (k + 1) + 1$, and $4 k (k + 1)$ is divisible by 8. Thus $n^2 \equiv 1 \pmod{8}$.
If $p > 3$ is prime, it is odd, and so by the above $p^2 \equiv 1 \pmod{8}$. As it is prime, $p \equiv 1 \pmod{3}$ or $p \equiv 2 \pmod{3}$, so $p^2 \equiv 1 \pmod{3}$. Now, as  $\gcd(3, 8) = 1$, combining the above congruences gives $p^2 \equiv 1 \pmod{24}$.
A: Never use induction at all. It is far too heavy a weapon for this kind of question.


*

*An odd number is a number of the form $4n±1$. Square it, and you get $16n^2±8n+1$, which clearly equals 1 modulo 8.

*Primes are irrelevant: this is true for all odd numbers which are not multiples of 3. Such a number is of the form $3n±1$. Square it, and you get $p^2=9n^2±6n+1$, which clearly equals 1 modulo 3. If this doesn't make it obvious to you that $p^2$ is 1 modulo 24, consider $p^2-1$. It is a multiple of 8, and it is also a multiple of 3, so it must be a multiple of 24.

A: For the second question, any prime $>3,$ can be expressed as $6a\pm1$ where $a$ is a positive integer
So, $p^2=(6a\pm1)^2=36a^2\pm12a+1=24a^2+24\cdot\frac{a(a\pm1)}2+1\equiv1\pmod{24}$ as $a(a\pm1)$ is divisible by $2$
Evidently, we don't need prime, any odd number not divisible by $3$ will satisfy this
