Suppose $n|a^2-1$ Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$

Question

Suppose $n|a^2-1$ where $a>1$ and n is odd. Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$.

Part 2

Show that if $a<n-1$ then this gives a nontrivial factorization of n

What I did:

I found the gcd$(a-1,a+1)$ which is $2$ if $a$ is odd and $1$ if $a$ is even. And that's it. I'm stuck

Answer 1

Suppose $n=p_1p_2...p_k$, then $p_1|a-1$ or $p_1|a+1$ (because $p$ is odd and $2|p$ doesn't hold). Continuing, $p_2|a-1$ or $p_2|a+1$.

Thus $(a-1)=p_i...p_l$ and $(a+1)=p_m...p_n$ where $[m,n,l,i] \in [1...k]$

Then since

$p_m...p_n|a+1$ and also $p_m...p_n|n$

$p_i...p_l|a-1$ and also $p_i...p_l|n$

We can conclude that gcd$(a-1,n)=p_i...p_l$ and gcd$(a+1,n)=p_m...p_n$

Thus putting all together we get the required result.

Answer 2

Since $n|(a^2-1)$, we have $\gcd(a^2-1, n)=n$.

First assume that $a$ is even. Then $\gcd(a-1, a+1)=1$. Therefore $$\gcd(a^2-1, n)=\gcd(a-1, n)\gcd(a+1, n)$$ and we are done.

Now suppose $a$ is odd. Then $\gcd(a^2-1, n)=\gcd((a^2-1)/4, n)$. This is because $n$ is odd. Since $\gcd((a-1)/2, (a+1)/2)=1$, we get that $$\gcd((a-1)/2, n)\gcd((a+1)/2, n)=n$$ Again using the fact that $n$ is odd to write $\gcd((a-1)/2, n)=\gcd(a-1, n)$ and $\gcd((a+1)/2, n)=\gcd(a+1, n)$, we are done.