Factoring 1001 in $\Bbb Z[\sqrt 7]$

Question

I am solving the problem of factoring 1001 into prime elements in $\Bbb Z[\sqrt 7]$.

I have a couple of questions regarding this.

1. 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.

2. 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.

Answer 1

1. 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]$.

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.

Answer 2

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$