\documentclass[12pt]{article}
\usepackage[table]{xcolor}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{hyperref}
\usepackage{authblk}
\usepackage[all]{xy}
\usepackage{enumitem}
\usepackage{stmaryrd}
\usepackage[makeroom]{cancel}
\usepackage{bbm}
\usepackage{fancyvrb}
\usepackage{xstring} % For the replace command
\usepackage{tikz}
%\usetikzlibrary{intersections}
\usepackage{xcolor,cancel}
\newcommand\hcancel[2][black]{\setbox0=\hbox{$#2$}%
\rlap{\raisebox{.45\ht0}{\textcolor{#1}{\rule{\wd0}{1pt}}}}#2}
\usepackage[normalem]{ulem}
\usepackage{xsim}
\xsimsetup{solution/print=true} %%%%%%
\newtheorem*{rk}{Remark}
\usepackage{xlop}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\f}{\mathfrak{f}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\g}{\mathfrak{g}}
\newcommand{\K}{\mathbb{K}}
\renewcommand{\l}{\mathfrak{l}}
\newcommand{\p}{\mathfrak{p}}
\renewcommand{\P}{\mathfrak{P}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\lcm}{\operatorname{lcm}}
\topmargin -2.5cm
\textheight 25cm
\textwidth 15cm
\begin{document}
\begin{center}
{\Huge Introduction to number theory \\ Exercise sheet 4}
\vspace{0.5cm}
\url{https://www.maths.tcd.ie/~mascotn/teaching/2020/MAU22301/index.html}
\vspace{0.5cm}
Version: \today
\vspace{1cm}
Answers are due for Friday November 20th, 2PM.
The use of electronic calculators and computer algebra software is allowed.
\end{center}
\vspace{1cm}
\begin{exercise}[subtitle=Do it before next year! (50pts)]
Find the complete factorisation of $20+21i$ in $\Z[i]$.
\end{exercise}
\begin{solution}
Let $\alpha=20+21i$. We know that it has a factorisation of the form
\[ \alpha = u \pi_1 \cdots \pi_r \]
where $u \in \Z[i]^\times = \{ \pm1, \pm i\}$ and the $\pi_j$ are irreducibles. This means that for each $j$, $\pi_j$ is associate to an irreducible $\pi'_j$ which is either $1+i$, a prime number $\equiv -1 \bmod 4$, or an irreducible of norm a prime number $\equiv +1 \bmod 4$. This $\pi_j = u_j \pi'_j$ for some $u_j \in \Z[i]^\times$; putting $u_j$ into $u$, we may assume that $\pi_j= \pi'_j$ is of the above form.
We compute that
\[ N(\alpha) = 20^2+21^2 = 841 = 29^2. \]
Since $29$ is prime and is $\equiv 1 \bmod 4$, this means that our factorisation actually has the shape
\[ \alpha = u \pi_1 \pi_2 \]
where $N(\pi_1) = N(\pi_2) = 29$; thus $\pi_1$ and $\pi_2$ are above $29$.
To find the irreducibles above $29$, we must decompose $29$ as a sum of two squares. As $29=5^2+2^2$, we have $29 = \pi \bar \pi$ where $\pi = 5+2i$ is irreducible of norm 29; so the irreducibles above 29 are associate to either $\pi$ or $\bar \pi$ (but not both since $\bar \pi$ is not associate to $\pi$). Therefore we have $\pi_1, \pi_2 \in \{ \pi, \bar \pi \}$ up to associates; putting the units in $u$ again, we can suppose that $\pi_1, \pi_2 \in \{ \pi, \bar \pi \}$.
We now have several ways to conclude. I'll show them all here, but as a student, you should pick one!
\begin{enumerate}
\item We can compute $\pi^2, \pi \bar \pi, \bar \pi^2$, and compare them with $\alpha$. We spot that $\bar \pi^2 = 21-20i = -i \alpha$, whence $\alpha = \bar \pi^2 / -i = i \bar \pi^2$.
\item We may compute that $\alpha/\pi = \frac{142}{29} + \frac{65}{29}i \not \in \Z[i]$, which shows that $\pi \nmid \alpha$; therefore $\pi_1=\pi_2 = \bar \pi$. And finally $u = \alpha / \bar \pi^2 = i$.
\item We may notice that if $\{ \pi_1, \pi_2 \} = \{ \pi, \bar \pi \}$, then $\alpha$ is divisible by $\pi_1 \pi_2 = \pi \bar \pi = 29$; and since clearly $\alpha/29 \not \in \Z[i]$, this cannot happen. Thus $\pi_1 = \pi_2 \in \{ \pi, \bar \pi \}$. And $\alpha / \bar \pi = 2+5i \in \Z[i]$, we have $\bar \pi \mid \alpha$, so $\pi_1=\pi_2=\bar \pi$.
Alternatively, $\alpha/\pi = \frac{142}{29} + \frac{65}{29}i \not \in \Z[i]$, so $\pi \nmid \alpha$, so $\pi_1 = \pi_2 \neq \pi$, so $= \bar \pi$.
Either way, we conclude again that $u = \alpha / \bar \pi^2 = i$.
\end{enumerate}
Conclusion: our factorisation is
\[ 20+21i = i(5-2i)^2 \]
where $5-2i$ is irreducible.
\end{solution}
\begin{exercise}[subtitle=How many ways? (50pts)]
Let $n \in \N$ be an integer. By separating prime factors into different types, we may factor $n$ as
\[ n = 2^a \prod_{j=1}^{r} p_j^{b_j} \prod_{k=1}^s q_k^{c_k}, \]
where the $p_j$ are distinct primes all~$\equiv +1 \bmod 4$, the $q_k$ are distinct primes \linebreak all~$\equiv -1 \bmod 4$, and $a$, the $b_j$, and the $c_k$ are non-negative integers.
Find (and prove) a formula for the number of pairs $(x,y)$ of $x,y \in \Z$ such \linebreak that $n=x^2+y^2$. NB the order and the signs count, i.e. $(x,y)$, and $(-x,y)$ count as distinct pairs unless $x=0$, and so does $(y,x)$ unless $x=y$.
\emph{Hint: This is the same thing as counting the $\alpha \in \Z[i]$ of norm $n$. Think in terms of factorisation. You may want to test your formula on small values of $n$.}
\end{exercise}
\begin{solution}
We want to count the pairs $(x,y) \in \Z^2$ such that $x^2+y^2=n$. This amounts to counting the $\alpha = x+yi \in \Z[i]$ of norm $N(\alpha)=n$.
By the uniqueness of factorisation in $\Z[i]$, this is also the same as counting the factorisations having norm $n$. To be more specific, we know that each irreducible in $\Z[i]$ is associate to exactly one of $1+i$, a prime number $q \equiv -1 \bmod 4$, $\pi_p$, or $\bar \pi_p$, where $\pi_p \bar \pi_p$ is a factorisation of a prime $p \equiv 1 \bmod 4$ (that is to say we chose such a factorisation for each such $p$; there is a choice to be made since we could also take $(-\pi_p)(- \bar pi_p)$, or $(i \pi_p)(-i \bar \pi_p)$, or $(-i \pi_p)(i \bar \pi_p)$). This means that each element of $\Z[i]$ can be written in a unique way as a unit times a product of those.
Besides, we know that $N(1+i)=2$, $N(q)=q^2$, and $N(\pi_p)=N(\bar \pi_p)=p$. Using the fact that the norm is multiplicative and the fact that factorisation in $\Z$ is unique, we deduce that $\alpha$ has norm $n = 2^a \prod_{j=1}^{r} p_j^{b_j} \prod_{k=1}^s q_k^{c_k}$ iff. it factors as
\[ \alpha = u (1+i)^a \prod_{j=1}^{r} \pi_{p_j}^{d_j} \bar \pi_{p_j}^{e_j} \prod_{k=1}^s q_k^{c_k/2} \]
where $u \in \Z[i]^\times$ and $d_j+e_j=b_j$ for all $j$. So we now have to count all such combinations.
First of all, the exponent $c_k/2$ of $q_k$ must be an integer; so if $c_k$ is odd for at least one $k$, then such a factorisation is not possible (we are re-proving the theorem on the sum of two squares here!).
Besides, for each $j$, the number of pairs $(d_j,e_j)$ such that $d_j+e_j=b_j$ is $1+b_j$. Indeed, $e_j=b_j-d_j$, so these pairs are determined by $d_j$, which is an integer ranging from $0$ to $b_j$.
Finally, the number of possibilities for $u$ is $\# \Z[i]^\times = \# \{ \pm1, \pm i \} = 4$. Since $a$ and the $c_k$ are fixed, there are no more parameters to be played on.
In conclusion, the number of pairs $(x,y)$ such that $x^2+y^2=n$ is
\[ \left\{ \begin{array}{ll} 0 & \text{ if at least one of the $c_k$ is odd,} \\ \displaystyle 4 \prod_{j=1}^r(1+b_j) & \text{ if all the $c_k$ are even.} \end{array} \right. \]
For example, $2020=2^2 \times 5^1 \times 101^1$ an be expressed as a sum of two squares in exactly~$4(1+1)(1+1)=16$ ways.
\end{solution}
\bigskip
\textbf{These were the only mandatory exercises, that you must submit before the deadline. The following exercises are not mandatory; they are not worth any points, and you do not have to submit them. However, I highly recommend that you try to solve them for practice, and you are welcome to \href{mailto:mascotn@tcd.ie}{email me} if you have questions about them. The solutions will be made available with the solution to the mandatory exercises.}
\bigskip
\begin{exercise}[subtitle=How many squares?]
\begin{enumerate}
\item Find an integer $>2000$ which is the sum of 3 squares, but not of 2 squares.
\item Find an integer $>2000$ which is the sum of 4 squares, but not of 3 squares.
\end{enumerate}
\end{exercise}
\begin{solution}
\begin{enumerate}
\item We know that if there is a prime $p \equiv -1 \pmod 4$ such that $p \mid n$ but $p^2 \nmid n$, then $n$ won't be a sum of 2 squares. So let us take $p=3$ for instance. We can take $n=2001$: since the sum of digits is $3$, $3 \mid n$ but $9 \nmid n$, so $n$ is not a sum of 2 squares.
Besides, if we had $n=4^a (8b+7)$, then necessarily $a=0$ since $n$ is odd. But $n \equiv 1 \not \equiv 7 \pmod 8$, so $n$ is not of the form $4^a(8b+7)$. As a result, $n$ is a sum of $3$ squares.
\item Since every integer is a sum of 4 squares, it suffices to take an $n$ of the form $4^a(8b+7)$ for any $a$ and $b$. We can go the easy way and take $a=0$, so we just need $n \equiv 7 \pmod 8$. So for instance $n=2007$ works.
\end{enumerate}
\end{solution}
\bigskip
\begin{exercise}[subtitle=The meaning of divisibility]
Let $a,b \in \Z$. We may also view $a$ and $b$ as elements of $\Z[i]$. Write $a \mid_\Z b$ if $a$ divides~$b$ when we view them as elements of $\Z$, and $a \mid_{\Z[i]} b$ if $a$ divides $b$ when we view them as elements of $\Z[i]$.
Prove that in fact, $a \mid_{\Z} b$ iff. $a \mid_{\Z[i]} b$.
\end{exercise}
\begin{solution}
We prove both implications.
First of all, if $a \mid_{\Z} b$, then $b=ac$ for some $c \in \Z$. Thus $c \in \Z[i]$, so $a \mid_{\Z[i]} b$.
Conversely, suppose that $a \mid_{\Z[i]} b$. This means that $b=a \gamma$ for some $\gamma \in \Z[i]$. We now distinguish two cases. If $a \neq 0$, then we have $\gamma = b/a \in \Q$, so $\gamma \in \Z[i] \cap \Q = \Z$, which proves that $a \mid_{\Z} b$. And if $a=0$, then $b=a\gamma=0$ as well, so again $a \mid_{\Z} b$ since $b=a c$ for one, and in fact any, $c \in \Z$.
\end{solution}
\bigskip
\begin{exercise}[subtitle=B\'ezout in $\Z[i]$]
Compute $\gcd(\alpha,\beta)$, and find $\xi,\eta \in \Z[i]$ such that $\alpha \xi + \beta \eta = \gcd(\alpha,\beta)$, when
\begin{enumerate}
\item $\alpha=4+6i$, $\beta=5+3i$,
\item $\alpha=8-i$, $\beta=5-2i$.
\end{enumerate}
\end{exercise}
\begin{solution}
This is the same principle as in $\Z$: we do euclidean divisions until we get a null remainder, and then we go back up the relations we have found to get $\xi$ and $\eta$.
\begin{enumerate}
\item Let us first perform a euclidean division of $\alpha$ by $\beta$. We have
\[ \frac{\alpha}{\beta} = \frac{(4+6i)(5-3i)}{34} = \frac{(2+3i)(5-3i)}{17} = \frac{19+9i}{17} \approx 1+i, \]
so the quotient is $1+i$ and the remainder is $(4+6i) - (5+3i)(1+i) = 2-2i$. We record this relation for later use.
Next, we divide the divisor by the remainder, that is to say $5+3i$ by $2-2i$. We have
\[ \frac{5+3i}{2-2i} = \frac{(5+3i)(2+2i)}8=\frac12+2i \approx 2i, \]
so our quotient is $2i$ (but we could also take $1+2i$) and the remainder is $(5+3i)-(2-2i)2i = 1-i$. We record this relation for later use.
Next step: divide $2-2i$ by $1-i$. Obvously, this is an exact division, with quotient 2 and remainder 0.
This means that $\boxed{ \gcd(\alpha, \beta)=1-i }$ (note that $1-i=-i(1+i)$ is associate to $1+i$, so $1+i$ is also a gcd). Besides, we have
\[ 1-i = (5+3i)-(2-2i)2i = (5+3i)-\big( (4+6i) - (5+3i)(1+i) \big)2i = (5+3i)(-1+2i)-(4+6i)(2i) \]
so we can take $\boxed{\xi =-2i, \ \eta=-1+2i}$.
\item (10 pts) Same process. First, we divide $8-i$ by $5-2i$:
\[ \frac{8-i}{5-2i} = \frac{(8-i)(5+2i)}{29} = \frac{42+11i}{29} \approx 1 \]
so the quotient is $1$ and the reminder is $(8-i)-(5-2i)=3+i$. We record this relation for later use.
Next, we divide $5-2i$ by $3+i$:
\[ \frac{5-2i}{3+i}=\frac{(5-2i)(3-i)}{10} = \frac{13-11i}{10} \approx 1-i, \]
so the quotient is $1-i$ and the remainder is $(5-2i)-(3+i)(1-i)=1$. We record this relation for later use.
Finally, we should divide $3+i$ by $1$. Of course the quotient is $3+i$ and remainder 0, so we stop. We have found that $\gcd(\alpha,\beta)=1$, which means that $\alpha$ and $\beta$ are coprime.
To find $\xi$ and $\eta$, we compute
\[ 1 = (5-2i)-(3+i)(1-i) = (5-2i)-\big( (8-i)-(5-2i) \big)(1-i) = (5-2i)(2-i)-(8-i)(1-i) \]
so we can take $\boxed{\xi =-1+i, \ \eta=2-2i}$.
\end{enumerate}
\end{solution}
\bigskip
\begin{exercise}[subtitle=Forcing a common factor]
Let $\alpha, \beta \in \Z[i]$.
\begin{enumerate}
\item Prove that $N\big(\gcd(\alpha, \beta)\big) \mid \gcd\big(N(\alpha),N(\beta)\big)$.
\item Explain why we can have $N\big(\gcd(\alpha, \beta)\big) < \gcd\big(N(\alpha),N(\beta)\big)$.
\item Suppose now that $\gcd\big(N(\alpha),N(\beta)\big)$ is a prime $p \in \N$. Prove that $p \not \equiv 3 \pmod 4$.
\item Still assuming that that $\gcd\big(N(\alpha),N(\beta)\big)$ is a prime $p \in \N$, prove that either $\alpha$ and $\beta$ are not coprime, or $\alpha$ and $\bar \beta$ are not coprime (or both).
\item Suppose more generally that $\gcd\big(N(\alpha),N(\beta)\big)$ is a integer $n \geqslant 2$, which we no longer assume to be prime. Is it true that either $\alpha$ and $\beta$ are not coprime, or $\alpha$ and $\bar \beta$ are not coprime (or both)? Is it true that at least one of $N\big(\gcd(\alpha, \beta)\big)$ and $N\big(\gcd(\alpha,\bar \beta)\big)$ is $n$?
\end{enumerate}
\end{exercise}
\begin{solution}
\begin{enumerate}
\item Since the norm is multiplicative, we know that if $\delta \mid \alpha$ then $N(\delta) \mid N(\alpha)$. As a result, if $\delta \mid \alpha$ and $\delta \mid \beta$, then $N(\delta) \mid N(\alpha)$ and $N(\delta) \mid N(\beta)$, so $N(\delta) \mid \gcd\big(N(\alpha),N(\beta)\big)$. This applies in particular to $\delta=\gcd(\alpha,\beta)$, whence the result.
\item Let $p$ be a prime such that $p \equiv 1 \pmod 4$, for instance $p=5$. Then we know that in $\Z[i]$, $p$ decomposes as $p= \pi \bar \pi$, where $\pi$ and $\bar \pi$ are both irreducible of norm $p$ and are not associate to each other. Let us take $\alpha = \pi$, $\beta=\bar \pi$. Then since they are irreducible and not associate to each other, they are coprime, so $N\big(\gcd(\alpha, \beta)\big)=1$, even though $\gcd\big(N(\alpha),N(\beta)\big)=\gcd(p,p)=p$.
\item From $\gcd\big(N(\alpha),N(\beta)\big)=p$, we infer that possibly after swapping $\alpha$ and $\beta$ we must have $p \mid N(\alpha)$ but $p^2 \nmid N(\alpha)$. By considering the factorization of $\alpha$ in $\Z[i]$, we deduce that $\alpha$ is divisible by an irreducible $\pi$ of norm $p$. No such irreducible exists if $p \equiv -1 \pmod 4$, whence the result.
\item We have $p \mid N(\alpha)$, so $\alpha$ must be divisible by an irreducible $\pi$ dividing $p$ in $\Z[i]$. Similarly, there is an irreducible $\pi' \mid p$ such that $\pi' \mid \beta$. But if $p =2$, then there is only one $\pi \mid p$ up to invertibles, so $\pi'$ must be associate to $\pi$ so that $\pi$ divides both $\alpha$ and $\beta$, whereas if $p \equiv 1 \pmod 4$ (which is the only other possible case by the previous question), then $\pi'$ is associate either ot $\pi$, in which case $\pi$ divides both $\alpha$ and $\beta$ again, or to $\bar \pi$, in which case $\pi$ divides both $\alpha$ and $\bar \beta$.
\item Let $p \mid n$ be a prime. Then we have again $p \mid N(\alpha)$ and $p \mid N(\beta)$, so as in the previous question we find an irreducible of norm $p$ which divides both $\alpha$ and either $\beta$ or $\bar \beta$ (or both), so the answer to the first question is yes.
However, the answer to the second question is no. Consider for instance two distinct primes $\ell,p \in \N$ which are both $\equiv 1 \pmod 4$, so that they decompose as $\ell = \lambda \bar \lambda$, $p = \pi \bar \pi$ in $\Z[i]$, and the irreducibles $\lambda, \bar \lambda, \pi, \bar \pi$ are pairwise coprime, and take $\alpha = \lambda \pi$, $\beta = \lambda \bar \pi$, so that $\bar \beta = \bar \lambda \pi$. Then we have $N(\alpha)=N(\beta)=\ell p$, so that $\gcd\big(N(\alpha),N(\beta)\big)=\ell p$, but $\gcd(\alpha,\beta)=\lambda$ and $\gcd(\alpha,\bar \beta)=\pi$ both have norm $<\ell p$ ($\ell$ for the former, $p$ for the latter).
\end{enumerate}
\end{solution}
\bigskip
\begin{exercise}[subtitle=Integers of the form $x^2+xy+y^2$ (difficult)]
Let $\omega = e^{\pi i /3} = \frac{1+i \sqrt{3}}2 \in \C$, and let $\Z[\omega]=\{ a + b \omega \ \vert \ a,b \in \Z \}$. Note that $\omega$ satisfies $\omega^2-\omega+1=0$ and $\omega^3=-1$.
We define the norm of an element $\alpha \in \Z[\omega]$ by $N(\alpha)=\alpha \bar \alpha = \vert \alpha \vert^2$.
\begin{enumerate}
\item Check that $\Z[\omega]$ is closed under addition, subtraction, and multiplication.
\item Prove that $N(a+b \omega) = a^2+ab+b^2$. Deduce that the set of integers of the form $x^2+xy+y^2$, $x,y \in \Z$, is stable under multiplication.
\item Prove that an element of $\Z[\omega]$ is invertible iff. its norm is $1$. Deduce that the set of units of $\Z[\omega]$ is
\[ \Z[\omega]^\times = \{ \omega, \omega^2, \omega^3=-1, \omega^4, \omega^5, \omega^6=1 \}. \]
\item Prove that Euclidean division is possible in $\Z[\omega]$.
\emph{Hint: $\{1,\omega \}$ is an $\R$-basis of $\C$.}
\item Deduce that we have unique factorisation into irreducibles in $\Z[\omega]$.
\item Let $p \neq 3$ be a prime. Prove that if $p \neq 2$, then $\big( \frac{-3}{p} \big) = \big( \frac{p}{3} \big)$, and deduce that the equation $x^2+x+1=0$ has solutions in $\Z/p\Z$ iff. $p \equiv 1 \pmod 3$.
\item Prove that the primes $p \in \N$ decompose in $\Z[\omega]$ as follows:
\begin{enumerate}
\item if $p=3$, then $3=\omega^5(1+\omega)^2$ (note that $\omega^5$ is a unit),
\item if $p \equiv 1 \pmod 3$, then $p = \pi \bar \pi$, where $\pi \in \Z[\omega]$ is irreducible and has norm $p$,
\item if $p \equiv -1 \pmod 3$, then $p$ remains irreducible in $\Z[\omega]$.
\emph{Hint: Prove that if $p=a^2+ab+b^2$, then at least one of $a$ and $b$ is not divisible by $p$.}
\end{enumerate}
\item What are the irreducibles in $\Z[\omega]$?
\item Deduce from the previous questions that an integer $n \in \N$ is of the form $x^2+xy+y^2$, $x,y \in \Z$ iff. for all primes $p \equiv -1 \pmod 3$, the $p$-adic valuation $v_p(n)$ is even.
\item Adapt the first exercise to find a formula for the number of pairs $(x,y)$, $x,y \in \Z$ such that $x^2+xy+y^2=n$ in terms of the factorization of $n$ in $\Z$.
\end{enumerate}
\end{exercise}
\begin{solution}
\begin{enumerate}
\item It is clear that $\Z[\omega]$ is stable under addition and subtraction, and for multiplication we have \[ (a+b \omega)(c+d \omega) = ac+(ad+bc) \omega +bd(\omega-1)=(ac-bd)+(ad+bc+bd) \omega \]
since $\omega^2=\omega-1$, so $\Z[\omega]$ is a ring. Besides, the product of 2 nonzero complexes is nonzero, so $\Z[\omega]$ is indeed a domain.
\item Since $\omega \in \C \setminus \R$, the complex roots of the polynomial $x^2-x+1$ are $\omega$ and $\bar \omega$, so we have $\omega+\bar \omega=1$ and $\omega \bar \omega=1$. Therefore,
\[ N(a+b \omega) = (a+ b \omega)(a+b \bar \omega) = a^2+ab (\omega + \bar \omega) + b^2 \omega \bar \omega = a^2+ab+b^2. \]
Besides, since clearly $N(\alpha \beta) = N(\alpha) N(\beta)$, we deduce that the set of integers of the form $a^2+ab+b^2$, $a,b \in \Z$, is stable under multiplication.
\item If $\alpha$ is invertible, then $N(\alpha) N(\alpha^{-1}) = N(1) = 1$, whence $N(\alpha)=1$ since norms are positive integers. Conversely, if $N(\alpha)=1$, then $\alpha$ is invertible of inverse $\bar \alpha$. Therefore, the invertibles are the $a+b \omega$ with $a^2+ab+b^2=1$. From
\[ a^2+ab+b^2 = (a+b/2)^2 + \frac34 b^2 \] we see that $\vert b \vert \leqslant 1$.
For $b=-1$, we must have $a=0$ or $1$, for $b=0$, we must have $a=\pm1$, and for $b=1$, we must have $a=0$ or $-1$, so there are exactly 6 invertibles. But $\omega$ is invertible since $1= \omega \bar \omega = \omega (1-\omega)$, so all powers of $\omega$ are a also invertibles, and since $\omega=e^{\pi i /3}$, the sequence of powers of $\omega$ is periodic of period exactly 6, so all 6 invertibles show up this way.
\item Observe first that if we extend the norm to all of $\C$ by setting $N(z)=z \bar z$, we have
\[ N(\lambda + \mu \omega) = \lambda^2+ \lambda \mu + \mu^2 \quad (\star) \]
for all $\lambda, \mu \in \R$.
Let now $\alpha, \beta \in \Z[\omega]$, $\beta \neq 0$; we want to show that there exist $\gamma,\rho \in \Z[\omega]$ with $\alpha = \beta \gamma + \rho$ and $N(\rho)