Problem
NT-B2-M01-P006 GCD of Differences of Powers
#6
★★★☆☆ Level 3 of 5
Prove that for \(n>1\), \( \gcd(n^3-1,n^2-1)=n-1 \).
Factor out \(n-1\), then check the remaining factors.
We have \(n^3-1=(n-1)(n^2+n+1)\) and \(n^2-1=(n-1)(n+1)\). Hence the gcd equals \((n-1)\gcd(n^2+n+1,n+1)\). The last gcd is \(1\), because for \(n\equiv-1\), the expression \(n^2+n+1\) has remainder \(1\). Therefore the gcd is \(n-1\).
After factoring out the common factor, it is important not to miss an additional common divisor.