<s>[INST] Suppose $n|a^2-1$ Show that $n=$gcd$(a-1,n)$gcd$(a+1,n)$ 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
 [/INST] 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.
</s>