If $\bf B$ is uniform, show that $${\bf A}({\bf r})=-\frac 1 2({\bf r}\times{\bf B})$$ works. That is, check that $\nabla \cdot {\bf A} = 0$ and $\nabla \times {\bf A} = {\bf B}$. Is this result unique, or are there other functions
with the same divergence and curl?
Now, it's surely easy to check this is the correct and unique solution, once you know it, for a particular gauge fixing (in this case, the so-called Coulomb gauge).
But how can you prove viceversa?
$$
\nabla\times{\bf A}={\bf B}\operatorname{uniform} \xrightarrow{\nabla\cdot{\bf A}=0}{\bf A}({\bf r})=-\frac 1 2({\bf r}\times{\bf B})
$$
Let us fix a frame of reference in which ${\bf B}=0\,\hat{x}+0\,\hat y+{\rm B}\,\hat z$. Then
$$
\operatorname{det}
\begin{bmatrix}
\hat x & \hat y & \hat z\\
{\partial}_x & {\partial}_y & {\partial}_z\\
{\rm A}_x & {\rm A}_y & {\rm A}_z\\
\end{bmatrix}
=
\begin{bmatrix}
0\\
0\\
\rm B\\
\end{bmatrix}
\implies
\left\{
\begin{aligned}
\partial_y{\rm A}_z-\partial_z{\rm A}_y&=0\\
\partial_z{\rm A}_x-\partial_x{\rm A}_z&=0\\
\partial_x{\rm A}_y-\partial_y{\rm A}_x&={\rm B}
\end{aligned}
\right.
$$
Every uniform field is irrotational. This means
$$\nabla\times{\bf B}=\nabla\times({\nabla\times{\bf A}})=\nabla(\nabla\cdot{\bf A})-\nabla^2{\bf A}=0 \xrightarrow{\nabla\cdot{\bf A}=0} \nabla^2{\bf A}=0.$$
So
$$
\left\{
\begin{aligned}
\partial^2_{xx}{\rm A}_x+\partial^2_{yy}{\rm A}_x+\partial^2_{zz}{\rm A}_x&=0\\
\partial^2_{xx}{\rm A}_y+\partial^2_{yy}{\rm A}_y+\partial^2_{zz}{\rm A}_y&=0\\
\partial^2_{xx}{\rm A}_z+\partial^2_{yy}{\rm A}_z+\partial^2_{zz}{\rm A}_z&=0\\
\end{aligned}
\right.
$$
Lastly, the Coulomb gauge implies
$$
\partial_{x}{\rm A}_x+\partial_{y}{\rm A}_y+\partial_{z}{\rm A}_z=0.
$$
At this point, I have no idea where to go from here. It all seems very far away from the desired expression for $\bf A$. Any help would be appreciated.
Best Answer
You can't, because it is not true. There is more than one possible vector potential with $\nabla \cdot \mathbf{A} = 0$ and $\nabla \times \mathbf{A} = \mathbf{B}$ (which answers the second part of the question). More specifically, notice that $$\mathbf{A} = - \frac{1}{2}(\mathbf{r} \times \mathbf{B}) + \nabla \chi \tag{1}$$ does that for any $\chi$ such that $\nabla^2 \chi = 0$. Hence, there are infinitely many solutions in the Coulomb gauge that satisfy the required conditions.
To get at Eq. (1), start with the ansatz
$$\mathbf{A} = - \frac{1}{2}(\mathbf{r} \times \mathbf{B}) + \mathbf{f},$$ for some vector field $\mathbf{f}$. From the conditions $\nabla \cdot \mathbf{A} = 0$ and $\nabla \times \mathbf{A} = \mathbf{B}$, if follows that $\nabla \cdot \mathbf{f} = 0$ and $\nabla \times \mathbf{f} = \mathbf{0}$. The latter means we can write $\mathbf{f} = \nabla\chi$ for some $\chi$, and this fact when allied to the former implies $\nabla^2 \chi = 0$.
So how can one find $\mathbf{A}$ given $\mathbf{B}$?
One way is to notice that the differential equations satisfied by the vector potential are $$\left\lbrace\begin{aligned}&\nabla\cdot\mathbf{A} = 0 \\ &\nabla \times \mathbf{A} = \mathbf{B}\end{aligned} \right.$$
Notice this is analogous to $$\left\lbrace\begin{aligned}&\nabla\cdot\mathbf{B} = 0 \\ &\nabla \times \mathbf{B} = \mu_0 \mathbf{J}\end{aligned} \right.$$ which means you can just proceed with typical arguments based on Ampère's Law.
Also, it is worth pointing out that the solutions to Maxwell's equations will also not be unique, but in the static cases we can often get a unique solution by demanding the fields to vanish at infinity, for example. The same is true for the vector potential if we impose that it must vanish at infinity. As mentioned by ACuriousMind in the comments, this can be seen from the Helmholtz Theorem.