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?
expressing the gcd(n, m) = 2
2
$\begingroup$
elementary-number-theory
divisibility
1 Answers
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.
-
0The part I do not see is how you get $n$ = $4m$ + $2$. Could you talk a little more about that? – 2012-09-15
-
0The equation $n=4m +2$ is just math language for the statement "$n$ is divisible by 2, but not four, so the number that is two less than $n$, namely $n-2$ would be divisible by four. Therefore $n-2$ must be the product of $4$ and some other number, we'll call that other number $m$." – 2012-09-15
-
0Thanks! I am really grasping elementary number theory better in terms of writing integers are factors and so forth!! – 2012-09-15