Check divisibility by using $\gcd$. Let $k$ be an odd integer. As a part of an introductory class to proofs, I wanted to show that the number $k^2 - 1$ is divisible by $8$, and managed to do this by checking that it is congruent modulo $8$. However a student came to me today asking if it was possible to prove the claim by using the greatest common divisor of the two numbers $8$ and $k^2 - 1$, but I couldn't answer them since I have very little experience in number theory and the question came right out of the bushes. Is there a proof to this claim, that a high school student who is fairly fluent in math could grasp, and that uses the $\gcd$ to its advantage somehow? To clarify, the student tried using the fact that if $a$, $b$, $c$ and $d$ are numbers such that $a = bc + d$, then $\gcd(a,b) = \gcd(b,d)$.

Well $k= 2m+1$ is odd so $k^2 - 1= 4m^2 + 4m$ so $\gcd(8,4m^2+4m) = 4\gcd(2,m^2+m)= 4\gcd(2, m(m+1))$.

And $\gcd(2,m(m+1))$ is $2$ if $m(m+1)$ is even and $1$ if $m(m+1)$ is odd.

And either $m$ is even and $m(m+1)$ is even; or $m$ is odd and $m+1$ is even and $m(m+1)$ is even. SO $m(m+1)$ is even.

So $\gcd(8,k^2 -1)=\gcd(8,4m^2 +4m) = 4\gcd(2,m(m+1))=4*2 =8$.

The only real trouble is there's nothing there that couldn't have been explained (and probably easierly) without gcd.