If $n$ is an odd integer, and $n$ divides $x^2-1$ then $n = \gcd(n, x-1)\cdot\gcd(n, x+1)$ I know that $n$ can be written as $2k+1,$ and for some $m,$ $nm=x^2-1$
Also $\gcd(n, x-1) = na+ (x-1)b$ ...
Is this going in the right direction or is there a better direction?
 A: Your statement needs $n$ to be positive. Also, $n$ need not be odd to prove it (taking $n$ to be positive of course).
Let $g:=\gcd(n,x-1)$ and $d:=\gcd(n,x+1).$ Then $$na_0+(x-1)a_1=g\hspace{11pt}\text{and}\hspace{11pt}nb_0+(x+1)b_1=d$$ for some $a_0,a_1,b_0,b_1\in\mathbb Z.$ Multiplying both expressions we get $nk+(x^2-1)q=gd$ for some $k,q\in\mathbb Z$ and since $\gcd(n,x^2-1)=|n|$ it follows by Bezout's identity that $n\mid gd.$ 
Now suppose that $gd\nmid n$ and let $n=gdt+r,$ where $t,r\in\mathbb Z$ and $r\in(0,gd).$ Then $n-gdt=r,$ which implies that $\gcd(n,gd)\mid r$ and since $\gcd(n,gd)\geqslant gd$ then $r\geqslant gd,$ which is clearly false. Therefore $r=0$ and hence $gd\mid n.$
Hence $n=\pm gd.$ 
A: $x^2 - 1 = (x+1)(x-1)$.  Both x + 1 and x - 1 are even and have no factor other than 2 in common (because they differ by only 2).
So is it true that if m|ab and gcd(a,b) = 2 does m = gcd(m,a)*gcd(m,b) if m is odd?  I think so. Since m is odd it has no even factors  Then for each odd prime p, such that $p^n$ is the highest power of p that divides m, then either $p^n$|a or $p^n$|b but not both.  Likewise neither gcd(a, m) nor gcd(m,b) have any factors not shared with m. So $p^n|gcd(m,a)$ or $p^n|gcd(m,b)$ but not both.  So the primes and their powers that make up m are the exact same primes, with some distribution, that make up  gcd(m, a) and gcd(m,b).  So m = gcd(m, a)gcd(m, b). 
