\input /profs/cs1/kaltofen/text/def.tex
\twelvepoint
\hbox to \hsize{\hfill\vtop{\halign {\hfill {\bf #}\hfill\cr
65-4962-01 \& 66-4961-01 Computational Abstract Algebra\cr
Homework~3\cr
Due 2/22/1990\cr}}\hfill}
\def\Problem#1{\medskip\noindent{\bf Problem~#1:}}
\Problem1
The integer sequence
$$\langle q_1, q_2, \ldots, q_t, g\rangle$$
is called a remainder sequence for the integers $a$ and $b$ if
$$r_1=a-q_1 b, r_2=b- q_2 r_1, r_3=r_1-q_3 r_2,\ldots,
  r_{t-1} = r_{t-3}- q_{t-1} r_{t-2},
  0=r_{t-2}-q_t r_{t-1}, g=r_{t-1}.$$
Prove that the remainder sequence generated by the generic
Euclidean algorithm that uses absolutely smallest remainder division
(the function {\tt Numbers`Quotient}) as the division
minimizes $t$ for all non-trivial $a$ and $b$.
\Problem2
Prove that the function {\tt Gaussian`Quotient} is a Euclidean
division function with respect to the square of the absolute value
degree function. Furthermore, prove that the domain of Gaussian
integers is a unique factorization domain.
\Problem3
Consider a prime integer $p$ with $p\equiv 1\pmod{4}$. Prove that the
equation
$$p=x^2+y^2$$
is solvable in integers $x$ and $y$. [Hint: You may assume that
there exists an $l\in \ZZ_p$ such that $l^2+1\equiv 0\pmod{p}$.
To experimentally verify this statement, try
$$\hbox{\tt Factor[l\cx 2+1, Variables->\lb l\rb, Modulus->p].}$$
Show then that $\GCD(p, l+\I)$
yields $x\pm \I y$ over the Gaussian integers.]
\bye