1. ## Modulo proof help

Let n be an odd integer not divisible by three. Prove that n^2 is congruent 1 mod 24.

I started by assuming that n is an odd integer divisible by three. So I want to show that n^2 is NOT congruent to 1 mod 24. If n is odd then there exists an integer k such that n=2k+1. so n^2= 4k^2 +4k+1. Now where do I go from here?!

2. That doesn't work, because you are proving that if $\displaystyle n^2-1$ is multiple of 24, then n is not multiple of 3. That doesn't prove that the assertion is true, there could be no such integers 'n'.

First note that: $\displaystyle 24=2^3\cdot{3}$ so we'll prove that $\displaystyle n^2-1\equiv{0}(\bmod.8)$ (1) and $\displaystyle n^2-1\equiv{0}(\bmod.3)$ (2)

(2) Follows easily from Fermat's Little Theorem since $\displaystyle (n,3)=1$, or you can check the 2 possible cases $\displaystyle n\equiv{1;2}(\bmod.3)$

(1) We have: $\displaystyle n^2-1=(n-1)\cdot{(n+1)}$, but since $\displaystyle n$ is odd, then either $\displaystyle n\equiv{1}(\bmod.4)$ or $\displaystyle n\equiv{3}(\bmod.4)$ so either $\displaystyle n-1$ or $\displaystyle n+1$ is multiple of 4, but both are even, thus the product must be multiple of 8, since one is multiple of 4 and the other even.

3. Thanks so much!!!