Factoring 1001 in $\Bbb Z[\sqrt 7]$ I am solving the problem of factoring 1001 into prime elements in $\Bbb Z[\sqrt 7]$.
I have a couple of questions regarding this.


*

*It seems that $\Bbb Z[\sqrt 7]$ is an Euclidean domain.  But I do not know what norm it has. (It seems that you have to choose an element close to a quotient cleverly, to show the norm defined naturally indeed is a norm of an Euclidean domain.)  In general, for what squarefree $c$ is $\Bbb Z[\sqrt c]$ an Euclidean domain and what its norm looks like?  People usually talk about this ring by using the terms from the theory of quadratic fields, which I am not familiar with, and there seems to be an ambiguity about the term 'Euclidean.'  I am confused.  I'm not concerned with quadratic fields for the time being and need a description in the language of elementary ring theory.

*How can I solve the original problem?  More generally, what are the primes of $\Bbb Z[\sqrt c]$?
I would be most grateful if you could provide a clue.
 A: *

*Yes, the ring $\mathcal{O}_7=\mathbb{Z}[\sqrt{7}]$ is the ring of integers of $\mathbb{Q}[\sqrt{7}]$, and it is Norm-Euclidean, $N(x)=N(a+b\sqrt{7})=a^2-7b^2$. In general,
the ring $\mathcal{O}_d$, for $d$ squarefree, is Norm-Euclidean, if and only if
$$
d= -11,-7,-3,-2,-1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73.
$$
The norm is $N(a+b\sqrt{d})=a^2-db^2$. Note however, that
if $d\equiv 1(4)$, then $\mathcal{O}_d=\mathbb{Z}[(1+\sqrt{d})/2]$.

*If $\alpha\in \mathcal{O}_d$ has a norm which is prime in $\mathbb Z$, then $\alpha$ is irreducible in $\mathcal{O}_d$. This is in general a sufficient condition, but not a necessary one. 
The answer how to factor, say $1001$ has been given here.
A: This problem is particularly easy to solve if you know the general principles: a prime $p$ of $\mathbb Z$ may be ramified in the integers of $\mathbb Q(\sqrt n\,)$, but for the unramified primes, there are two possibilities. If $n$ is not a square modulo $p$, then you need to go to $\mathbb F_{p^2}$ to catch a square root of $n$. This means that there’s residue-field extension, so the prime can’t split, and $p$ is already prime in the quadratic integer ring.
In our case, where $1001=7\cdot11\cdot13$, you already know that $7=(\sqrt 7\,)^2$, and we need to know whether $11$ and $13$ remain prime in the quadratic ring. You can check directly (without using Quadratic Reciprocity) that $7$ is not a square modulo either $11$ or $13$, but the way to use QR is:
$$
\left(\frac7{11}\right)=-\left(\frac{11}7\right)=-\left(\frac47\right)=-1\,,
$$
the explanation being that $7\equiv11\equiv3\pmod4$, so the first two quadratic characters are reversed; and that $4$ is a square so its character is $1$. On the other hand,
$$
\left(\frac7{13}\right)=\left(\frac{13}7\right)=\left(\frac{-1}7\right)=-1\,.
$$
Here the first equality happens because one of the primes is congruent to $1$ modulo $4$. But if you don’t know QR, you just check that $7$ is a nonsquare modulo both $11$ and $13$ directly. This says that $11$ and $13$ remain prime in $\mathbb Z[\sqrt7\,]$, so your factorization is easy: $(\sqrt7\,)^2\cdot11\cdot13$
