What is the smallest $d$ such that $4$ has more than one distinct factorization in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$? Or if there is no such $d$, how do I prove it?
Obviously there is no point to looking for this in an UFD. I've looked in other rings, and each time I think I found it, I divide one of the factors by $2$ and find a unit, e.g.,:
$$\frac{38 + 12 \sqrt{10}}{2} = 19 + 6 \sqrt{10}$$
$$\frac{8 + 2 \sqrt{15}}{2} = 4 + \sqrt{15}$$
$$\frac{102 + 20 \sqrt{26}}{2} = 51 + 10 \sqrt{26}$$
$$\frac{22 + 4 \sqrt{30}}{2} = 11 + 2 \sqrt{30}$$
$$\frac{70 + 12 \sqrt{34}}{2} = 35 + 6 \sqrt{34}$$
etc.
In general, it seems that if the "integer" part and the "surd" part have the same parity, it will turn out to just be a unit doubled.

$$\left( \frac{\sqrt{65}+7}{2} \right) \left( \frac{\sqrt{65}-7}{2} \right) =4.$$
Since $65 \equiv 1 \bmod 4$, this is an algebraic integer, and clearly $2$ does not divide $\left( \frac{\sqrt{65}+7}{2} \right)$. We need to check that $2$ and $\left( \frac{\sqrt{65}+7}{2} \right)$ are irreducible in $\mathbb{Z} \left[  \frac{1+\sqrt{65}}{2} \right]$. Since they both have norm $4$, we need to check that there is no element in the ring with norm $\pm 2$. We need to show we can't have $N \left(\frac{a+b\sqrt{65}}{2} \right) = \pm 2$ or equivalently, we can't have $a^2-65 b^2 = \pm 8$. This relation is impossible modulo $5$.

How I found this: Let's think about how the ideal $(2)$ can factor into prime ideals.

*

*$(2)$ stays prime. Then $4 = 2 \times 2$ is the only factorization.


*$(2) = \mathfrak{p} \mathfrak{q}$ is a product of principal ideals, $\mathfrak{p} = (a)$ and $\mathfrak{q}=(b)$. Then $4 = \pm a^2 b^2$ is the unique prime factorization (and we can show the sign is $+$, but that isn't important.)


*$(2) = \mathfrak{p}^2$ with $\mathfrak{p}$ non principal. Again,  $4 = 2 \times 2$ is the only factorization.
So the only option is that $2$ splits into distinct, non principal, primes. $2$ splits in the ring of integers of $\mathbb{Q}(\sqrt{d})$ (for $d$ square free) if and only if $d \equiv 1 \bmod 8$.
So we are looking for $d \equiv 1 \bmod 8$, square free, and class number $>1$. The first such $d$ is $65$ (I looked in this table) and it works.

After thinking a bit more, there are infinitely many such examples. Find $k$ such that $8k+5$ and $8k+13$ are both squarefree. There are infinitely many such pairs, see this answer. Take $D = (8k+5)(8k+13)$. It is also squarefree, since no $p^2$ divides either factor and, if $p$ divided both $8k+5$ and $8k+13$, then it would divide $(8k+13)-(8k+5)=8$, but $8k+5$ and $8k+13$ are odd.
Now, $\left( \frac{8k+9 + \sqrt{D}}{2} \right) \left( \frac{8k+9 - \sqrt{D}}{2} \right) = 4$. As before, it is obvious that $2$ doesn't divide $(8k+9 \pm \sqrt{D})/2$. Finally, we must check that there is no solution to $x^2 - D y^2 = \pm 8$. We break into cases, based on the prime factorization of $8k+5$:
Case 1 $8k+5$ is divisible by a prime $p$ which is $5 \bmod 8$. Then $\left( \frac{2}{p} \right) = \left( \frac{-2}{p} \right) = -1$, so $x^2 - D y^2 \equiv x^2 \bmod p$ cannot be $\pm 8$.
Case 2 $8k+5$ is divisible by a prime $p$ which is $3 \bmod 8$, and another prime $q$ which is $7 \bmod 8$. Then $\left( \frac{2}{p} \right) = -1$ and $\left( \frac{-2}{q} \right) = -1$, so $x^2 - D y^2 = 8$ is impossible modulo $p$ and $x^2 - D y^2 = -8$ is impossible modulo $q$.
Case 3 All prime divisors of $8k+5$ are either $1$ or $3$ mod $8$. But then $8k+5$ is $1$ or $3$ modulo $8$, a contradiction.
Case 4 All prime divisors of $8k+5$ are either $1$ or $7$ mod $8$. But then $8k+5$ is $1$ or $7$ modulo $8$, a contradiction.
After staring for a little bit, you will see that one of these cases must hold; QED.
