commercial macsyma returns instantly with 1.
....
> Please ponder the consequences of this while waiting for
>
> (C1) tellrat(t^2=x^2+1)$
> (C2) gcd:subres$ /* This is the default anyway */
> (C3) algebraic:true$
> (C4) :lisp(trace prem)
>
> WARNING:
> TRACE: redefining function PREM in top-level, was defined in /home/wolfgang/maxima/src/binary-clisp/rat3c.fas
> ;; Tracing function PREM.
> (PREM)
> (C4) gcd(t+x,x^2+1);
>
>