2
$\begingroup$

What are alternative ways to write gcd($n$, $8$) = $2$ ?? This is part of larger proof. I do not see writing the gcd as a linear combination as much help: $2$ = $nr$ + $8s$ Ultimately, I am trying to show that $n^2$ mod $8$ = $4$ when the gcd($n$, $8$) = $2$. Does anyone have suggestions to get me on the write track?

1 Answers 1

3

The equality $\mathrm{gcd}(8,n) = 2$ basically means that $2$ divides $n$, but $4$ does not (else, gcd would be larger). It says nothing about any other divisibility. What you can get out of the the condition is that $n = 4m + 2$ for some integer $m $, or in other words that $n \equiv 2 \pmod{4}$.

To get the conclusion that you mentioned, express $n$ as $n = 4m + 2$ and use this formula to work out $n^2$: $n^2 = (4m+2)^2 = 16 m^2 + 16 m + 4$ Thus, you really get $n^2 \equiv 4 \pmod{16}$ which is even stronger than the claim you need.

  • 0
    Thanks! I am really grasping elementary number theory better in terms of writing integers are factors and so forth!!2012-09-15