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?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|
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. |
|||||||
|
