If $n$ is an odd integer, and $n$ divides $x^2-1$ then $n = \gcd(n, x-1)\cdot\gcd(n, x+1)$

Question

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?

Answer 1

$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).

Answer 2

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.$