Check divisibility by using $\gcd$.

Question

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)$.

Answer 1

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.

Answer 2

I don't know if this is what you are looking for, but I have another approach without using congruences. Since $k$ is odd integer and if $k = 1$, we have $k^2-1 = 0$ is divisible by $8$, I will assume $k \ge 3$. Then, $k^2-1 = (k+1)(k-1)$. Now, if $k \ge 3$, $k+1 \ge 4$ and $k-1 \ge 2$. Then the product will be always greater than or equal to $8$. Hence, there will always be a factor of $8$ in $k^2 -1$.

Answer 3

You can use it and make an induction to solve the problem. $(k+2)^2 - 1 - (k^2 - 1) = 4k+4$ is a multiple of $8$ ($k$ is odd) so $gcd ((k+2)^2 -1, 8) = gcd (k^2 -1, 8)$ And the result is trivial for $k = 1$.

Answer 4

The problem is that you want to demonstrate a specific case of $m\mid n$, and $m\mid n \iff \gcd(m,n)=m$. Can you show the RHS other than by showing the LHS?

I think perhaps yes. Many of the ideas in this answer have been alluded to or incorporated in other answers, but have not been assembled in this way.

The one idea not explicitly stated in other answers (it's sort of hinted at) is that for two consecutive even numbers, one contains a single factor of $2$ and the other contains more than one factor of $2$, i.e. $2^j,\ j \ge 2$. Without giving a formal proof, this can be seen from the fact that the even numbers (in order) are just $2$ times the natural numbers. If you look at an even number that is twice an odd number, it has only one factor of $2$. The next larger even number is therefore twice an even number, so it has more than one factor of $2$. The next even number is once again twice an odd number and only has one factor of $2$; and so forth.

$k^2-1=(k+1)(k-1)$ and $(k+1),(k-1)$ are two consecutive even numbers ($k$ is odd and their difference is $2$). Thus one of them can be represented as $2r$ and the other as $2^js$, where $r,s$ are odd and $j\ge 2$ (we can't know which is represented which way without knowing the value of $k$). Thus $k^2-1=(k+1)(k-1)=2^{j+1}rs$.

$\gcd(2^3,2^{j+1}rs)=2^{\min(3,(j+1))}$; for $j\ge 2,\ \min(3,(j+1))=3$. Substituting back, we get $\gcd(8,(k^2-1)=8\ $QED.