Prove that for every n, (n+1,n^2-n+1) is 1 or 3.
Dear Deepu,
$\displaystyle (n+1,n^2-n+1)=d$
$\displaystyle d\mid{n+1} \mbox{ and }d\mid{n^2-n+1}$
$\displaystyle d\mid{(n+1)^2-3n}$
$\displaystyle d\mid{3n}$
$\displaystyle d\mid{n+1}\Rightarrow d\mid{(3n+3)}$
$\displaystyle d\mid{3}$
$\displaystyle d=1 \mbox{ or }d=3$
Hope this helps.