Take the 2-minute tour ×
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.

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?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
The part I do not see is how you get $n$ = $4m$ + $2$. Could you talk a little more about that? –  CodeKingPlusPlus Sep 15 '12 at 20:10
    
The 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$." –  Arthur Sep 15 '12 at 20:40
    
Thanks! I am really grasping elementary number theory better in terms of writing integers are factors and so forth!! –  CodeKingPlusPlus Sep 15 '12 at 20:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.